【例5.13】蛇形填数

GitHub跳转原题关系图返回列表

使用二维数组模拟填数过程,通过方向数组控制走向,当遇到边界或已填过的格子时改变方向。

OJ: roj

题目 ID: 5047

难度:入门

标签:模拟二维数组

创建: 2026-10-08 20:57

更新: 2026-10-08 20:57

形式化题目

给定一个正整数 nn(1≤n≤201 \le n \le 20),要求在一个 n×nn \times n 的矩阵中,将 1,2,3,…,n×n1, 2, 3, \dots, n \times n 的数字依次填入。填入的起点为矩阵的右上角(第 00 行,第 n−1n-1 列),填入的方向按照:向下 →\to 向左 →\to 向上 →\to 向右 的顺序顺时针循环。当且仅当下一个要填的格子超出矩阵边界或已经被填过数字时,改变方向。

最终按行从上到下、从左到右的顺序输出该矩阵。每行输出 nn 个数,相邻数字之间用一个空格隔开,行末不留多余空格。

正解

思路

这是一个典型的二维数组模拟题。我们需要一个二维数组来保存填入的数字,并模拟依次填入每个数字的过程。

为了实现填数,我们需要维护当前所在的坐标 (x,y)(x, y),以及当前的移动方向。 从真实测试数据反推可以明确题目定义的蛇形填数方向为:从右上角起笔,按下 →\to 左 →\to 上 →\to 右依次推进,这在屏幕坐标系里是一个由外向内顺时针螺入的过程。

我们可以使用“方向数组”来简化代码,设 dx 和 dy 分别表示四个方向在 xx 轴和 yy 轴上的增量:

  • 向下:dx = 1, dy = 0
  • 向左:dx = 0, dy = -1
  • 向上:dx = -1, dy = 0
  • 向右:dx = 0, dy = 1

我们从数字 11 开始,直到填到 n×nn \times n。起点设为右上角 (0,n−1)(0, n-1)。在每一步中,先将当前数字填入格子 (x,y)(x, y),然后尝试向当前方向走一步走到 (nx,ny)(nx, ny):

  1. 如果 (nx,ny)(nx, ny) 越界(超出 0…n−10 \dots n-1 的范围),或者 (nx,ny)(nx, ny) 这个格子已经被填过了(非 00),说明当前方向不能继续走,此时需要顺时针改变方向(方向索引 d = (d + 1) % 4),重新计算下一步 (nx,ny)(nx, ny)。
  2. 否则,方向不变。
  3. 接着更新 (x,y)=(nx,ny)(x, y) = (nx, ny),准备填下一个数字。

输出时,只需遍历整个二维数组即可。注意控制单空格分隔、行末没有多余的空格,且末尾恰有一个换行。

本题数据由自制脚本生成。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 20:40
# update_at: 2026-10-08 20:40

import sys

# 四个方向的增量,按「下、左、上、右」顺时针循环,与 C++ 版一致
DX = (1, 0, -1, 0)
DY = (0, -1, 0, 1)


def spiral(n: int) -> list[list[int]]:
    """从右上角起笔,按「下、左、上、右」螺旋填入 1..n*n,返回 n×n 方阵。"""
    a = [[0] * n for _ in range(n)]
    x, y, d = 0, n - 1, 0  # 起点为右上角 (0, n-1),方向 0 即先向下
    for v in range(1, n * n + 1):
        a[x][y] = v
        nx, ny = x + DX[d], y + DY[d]  # 先看后走:越界或已填过就顺时针转一次
        if not (0 <= nx < n and 0 <= ny < n) or a[nx][ny]:
            d = (d + 1) % 4
            nx, ny = x + DX[d], y + DY[d]
        x, y = nx, ny
    return a


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    sys.stdout.write(''.join(' '.join(map(str, row)) + '\n' for row in spiral(n)))


if __name__ == '__main__':
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 20:40
 * update_at: 2026-10-08 20:40
 */
#include <iostream>

using namespace std;

typedef long long ll;

const int MAXN = 25;

// 方阵,a[i][j] 表示第 i 行第 j 列填入的数字,0 表示还没填过
int a[MAXN][MAXN];

// 四个方向的增量,按「下、左、上、右」顺时针循环:
// 0=下(dx=1,dy=0) 1=左(0,-1) 2=上(-1,0) 3=右(0,1)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

// 从右上角起笔,按「下、左、上、右」螺旋填入 1..n*n
void solve() {
    ll n;
    if (!(cin >> n)) return;

    ll x = 0, y = n - 1; // 起点:第 0 行、第 n-1 列(右上角)
    ll dir = 0;          // 当前方向下标,初值 0 即先向下

    for (ll v = 1; v <= n * n; ++v) {
        a[x][y] = v;

        // 先看后走:下一步越界或已填过,就顺时针转一次方向
        ll nx = x + dx[dir];
        ll ny = y + dy[dir];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n || a[nx][ny] != 0) {
            dir = (dir + 1) % 4;
            nx = x + dx[dir];
            ny = y + dy[dir];
        }
        x = nx;
        y = ny;
    }

    for (ll i = 0; i < n; ++i) {
        for (ll j = 0; j < n; ++j) {
            cout << a[i][j] << (j == n - 1 ? "" : " "); // 行末不留多余空格
        }
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();

    return 0;
}

复杂度

  • 时间复杂度:O(n2)O(n^2)。矩阵中共有 n2n^2 个格子,每个格子刚好被填入一次并被遍历输出一次,每次判断和移动(转向至多发生 O(n)O(n) 次)只需要常数时间。
  • 空间复杂度:O(n2)O(n^2)。需要一个 n×nn \times n 的二维数组来存储所有的数字。n≤20n \le 20,可以直接开全局数组 a[25][25],空间极小。

总结

蛇形的精确定义与反推

蛇形填数在不同题目的语境中有多种互不相同的常见定义(例如:右上逆时针、左下顺时针、或“S 形”对角线/行间回字)。做此类题目必须以数据为准而非凭印象。

我们可以通过真实数据,逐点反推数字 1→n21 \to n^2 的转向序列来确认本题规则:

  • n=1n=1:值 11 在 (0,0)(0,0),转向序列 =∅= \emptyset。
  • n=2n=2:值 11 在 (0,1)(0,1),转向序列 =下→左→上= \text{下} \to \text{左} \to \text{上}。
  • n=3n=3:值 11 在 (0,2)(0,2),转向序列 =下→左→上→右→下= \text{下} \to \text{左} \to \text{上} \to \text{右} \to \text{下}。
  • n=20n=20:值 11 在 (0,19)(0,19),转向序列 =(下左上右)19= (\text{下左上右})^{19}。

由此确认了:起点必须是右上角 (0,n−1)(0, n-1),转向序列恒为 下→左→上→右 循环。

各核心要素的承重实验

一旦搞错方向或起笔,就会引发数据错误。以下是通过反事实验证得出的各要素改动后果:

改动 结果 典型失败点
逆时针转弯 (d+1)%4 → (d+3)%4 9 组 FAIL n=2n=2:输出第一行为 0 1(应为 4 1)
起点改左上角 (0,0) 9 组 FAIL n=2n=2:输出第一行为 1 0
去掉「已填过」转向条件 8 组 FAIL n=3n=3:输出第一行为 7 8 9
扰动方向表 9 组 FAIL n=2n=2:输出第一行为 4 3
分隔符改双空格 全 9 组 FAIL(非 n=1n=1 点) —
行末留多余空格 全 10 组 FAIL —
文件末尾多一个空行 全 10 组 FAIL —

这些实验证明了:转弯旋向、起点角、已填判定、分隔符 均为程序的关键承重点。

反事实实验的选点教训

反事实实验必须选择“真正承重”的变量去修改,否则会得出错误结论。 例如,如果我们保持当前代码的起点是右上角不变,试图把初始方向“从下改为向右(先右后下)”,程序的输出并不会改变。这是因为一上来朝右走就会立刻越界,程序会立刻执行转向操作转回向下。 这使得“方向表前两项的先后”变得不可观测。这很容易让人误以为“方向表怎么写都行”,但实际上真正承重的是方向的旋向以及起点角,它们一旦被修改,立刻会导致大面积失败。

细节与边界

  • 静态全局数组:在 C++ 中,直接使用全局二维数组 int a[MAXN][MAXN],不仅符合项目惯例,在 O(n2)O(n^2) 较小时也避免了 std::vector 的额外开销。
  • 边界 n=1n=1:最小输入为 11,输出单独的 1 加上换行。不需要发生任何转向。
  • 输出格式:要求极其严格的单空格分隔、行尾无多余空格、末尾恰好一个 \n、无多余空行。在 Python 中,通过先组装成完整字符串再 sys.stdout.write 输出,能精确控制尾部换行;C++ 中可使用 (j == n - 1 ? "" : " ") 判断。