蛇形填数详解：信息学奥赛经典二维数组题全攻略

信息奥赛一本通 2045 的蛇形填数，是很多竞赛新手绕不开的一道经典题。题目本身不长：给一个 n，把 1 到 n 的平方按蛇形填进 n×n 的矩阵里，然后输出。说实话，我带过的初学学生里，第一次能独立把这道题完整写对的人并不多，十个人里能有两三个就算不错。多数人不是看不懂规则，而是代码一跑就出问题——要么数组越界直接崩溃，要么填到一半方向错乱，要么最后几个数是 0。这篇文章就从题目拆解、解题思路、代码落地一直写到踩坑记录和变式延伸，尽量把这道题讲透。适合刚学到二维数组和循环嵌套的竞赛新手，也适合带竞赛班的老师拿来当备课参考。

1. 题目拆解：蛇形填数到底在考什么

1.1 题面规则先看明白

先别急着写代码，把题目要求一条条梳理清楚。输入一个正整数 n，要求将 1 到 n² 这 n² 个数依次填入一个 n 行 n 列的矩阵。填充起点是左上角，也就是第 1 行第 1 列，然后沿着对角线方向走。具体规则是：先向右上方填，直到撞到矩阵边界，然后掉头向左下方填；再撞到边界后，再次掉头向右上方填，如此反复，像蛇一样来回穿梭，直到矩阵填满。

以 n=4 为例，完整输出应该是：

code复制1 2 6 7
3 5 8 13
4 9 12 14
10 11 15 16

很多人第一次看到这个输出会误以为是螺旋填数，实际上完全不是。螺旋填数是像洋葱一样从外圈一层层往里绕，而这里的蛇形是沿对角线来回走。名字虽然叫“蛇形填数”，但这条“蛇”走的不是横向 S 型，而是斜着的之字形。理解错规则，后面全白搭。

1.2 这道题背后真正的考点

在竞赛题里，表面考的是二维数组，深层其实考两个东西：坐标感和状态切换。

先看坐标感。二维数组 arr[x][y] 里，x 表示行，y 表示列。向右上走，坐标变化是 x 减 1、y 加 1；向左下走，坐标变化是 x 加 1、y 减 1。很多新手最大的问题不是不会算，而是把 x 和 y 搞反，或者数组下标从 0 开始，边界判断也跟着乱，最后调半天才发现是起点概念没统一。

再看状态切换。蛇形填数里方向其实只有两种状态：右上和左下。遇到边界之后不是 180 度掉头，而是切换到另一种对角方向继续走。这种行为很像贪吃蛇撞墙：不会穿墙而过，而是贴着墙拐个弯继续前进。其实质是一个有限状态机，用变量记录当前方向，每填一个数就检查下一步是否需要切换状态。理解了这一层，代码写起来就很顺。

2. 解题思路：先把“蛇”的路线在纸上跑一遍

2.1 手工模拟 n=4 的完整路径

写代码前，我强烈建议先在草稿纸上把整条路径标出来。我自己带学生时也坚持这个要求，一张图能省至少半小时的 debug 时间。

n=4 时，蛇的路径坐标序列是这样的（用 (行,列) 表示）：

(1,1) → (1,2) → (2,1) → (3,1) → (2,2) → (1,3) → (1,4) → (2,3) → (3,2) → (4,1) → (4,2) → (3,3) → (2,4) → (3,4) → (4,3) → (4,4)

对照刚才的样例输出，这个路径是吻合的。第 1 个数 1 在 (1,1)，第 2 个数 2 在 (1,2)，第 3 个数 3 在 (2,1)，以此类推，第 16 个数 16 在 (4,4)。

观察路径可以发现，方向并不是一直不变的。从 (1,1) 出发时想往右上走，但右上角已经出了矩阵上边界，所以实际先向右挪到 (1,2)。然后从 (1,2) 向右上会再次越界，这时切换为左下，走到 (2,1)。跑到最左列之后，左下也走不了，再切换为右上……所以这条蛇的轨迹，其实是一段一段对角线拼接出来的。

2.2 撞墙的四种情况都要考虑全

细看上面的路径，边界修正无非四种情况，而且每一类撞墙都对应不同的“转弯方式”。

向右上方向走时：

• 如果当前行已经是第 1 行，再往右上会越过上边界，下一步应向右移动一列；
• 如果当前列已经是第 n 列，再往右上会越过右边界，下一步应向下移动一行；
• 特殊位置是右上角 (1, n)，这时既在上边界又在右边界，只能向下移动一行。

向左下方向走时：

• 如果当前行已经是第 n 行，再往左下会越过下边界，下一步应向右移动一列；
• 如果当前列已经是第 1 列，再往左下会越过左边界，下一步应向下移动一行；
• 特殊位置是左下角 (n, 1)，这时既在下边界又在左边界，只能向右移动一列。

这里要特别提醒一个新手很容易踩的坑：特殊位置的判断顺序很重要。比如站在右上角 (1, n) 时，如果先判断“行等于 1”，下一步就会向右走，结果走到不存在的第 n+1 列，直接数组越界。正确的做法是优先判断“列等于 n”，先处理右边界，再去考虑上边界，这样才会向下走一步。

2.3 为什么不直接原地掉头？

有同学会问：撞墙之后为什么不是原地换个方向继续走，而是要先“横着”或“竖着”挪一格？

原因很简单：当前格子已经填过数字了，下一步必须落到一个没填过的格子上。比如在 (1,2) 这个位置，向右上走会越界，如果原地把方向改成左下，下一步计算还是从 (1,2) 出发，走到 (2,1)，这没问题；但如果不先挪一格就直接从左下出发，那你还是站在 (1,2) 嘛。实际上“横着挪一格”或者“竖着挪一格”就是在找下一段对角线的起点，等于把方向转换和位置更新合成了一步。

这个问题想明白了，边界处理的逻辑就清晰了，代码也不会写得乱七八糟。

3. 代码实现：从思路到一次 AC

3.1 最推荐的“先填后走”写法

蛇形填数的代码写法有不少，我最推荐的是“先填当前格子，再预判下一步位置”的写法。它逻辑最直白，也最不容易漏填。

cpp复制#include <bits/stdc++.h>
using namespace std;

int a[25][25];

int main() {
    int n;
    cin >> n;

    int x = 1, y = 1;      // 起点：第 1 行第 1 列
    int dir = 0;           // 0 表示向右上，1 表示向左下

    for (int cnt = 1; cnt <= n * n; ++cnt) {
        a[x][y] = cnt;     // 先填当前格子

        if (dir == 0) {    // 向右上方向，尝试找下一个位置
            if (y == n) {       // 已经到最右列，只能向下
                ++x;
                dir = 1;
            } else if (x == 1) { // 已经到最上行，只能向右
                ++y;
                dir = 1;
            } else {            // 正常情况，右上移动
                --x;
                ++y;
            }
        } else {           // 向左下方向，尝试找下一个位置
            if (x == n) {       // 已经到最后一行，只能向右
                ++y;
                dir = 0;
            } else if (y == 1) { // 已经到最左列，只能向下
                ++x;
                dir = 0;
            } else {            // 正常情况，左下移动
                ++x;
                --y;
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cout << a[i][j] << (j == n ? '\n' : ' ');
        }
    }

    return 0;
}

这段代码的关键在于：每次循环先填数，再去算下一步走到哪。就算最后一步填完 n² 之后还多算了一次下一步的位置，也无关紧要，因为循环已经结束了。这种“先做事再导航”的顺序，能最大程度避免“走到没填过的格子却发现没填数”的尴尬。

3.2 边界顺序为什么这样安排

有人会问，向右上的判断里，为什么先判 y == n 再判 x == 1，顺序反过来不行吗？

我们先看反过来会发生什么。假如当前在右上角 (1, n)，用“先判 x == 1”的写法：满足 x == 1，于是 y++，跑到 (1, n+1)，这个位置已经超出矩阵列号，下一次循环访问 a[x][y] 就数组越界了，在 OJ 上就是常见的 Runtime Error。

而正确顺序是先判 y == n，这时发现已经在最右列，于是 x++，走到 (2, n)，完全合法。左下方向同理，在左下角 (n, 1)，必须先判断 x == n 再判断 y == 1，否则也会跑到不存在的第 n+1 行。

这个优先级问题，本质上是在处理“一个位置同时满足两个越界条件”的情况。做题时多想想“如果两个条件同时成立会怎样”，很多隐藏 bug 都能提前避免。

3.3 也许你听过“方向数组”的写法

还有一类常见写法是用方向数组：

cpp复制int dx[2] = {-1, 1};
int dy[2] = {1, -1};

dx[0]、dy[0] 表示右上，dx[1]、dy[1] 表示左下。每次尝试用当前方向前进一步，如果越界就做边界修正，然后切到另一个方向。这种写法的优点是抽象程度高，以后做类似“机器人走路”的题目也能复用；缺点是对初学者来说修正逻辑比较绕，容易出现“明明已经在边界却还要再走一次”的重复填数问题。我一般不推荐新手一上来就硬套方向数组，先把前面的基础写法吃透，方向数组作为进阶理解更合适。

3.4 时间复杂度和数组开多大

整套流程需要填 n² 个数，每个格子恰好访问一次，时间复杂度是 O(n²)。空间上需要一个 n×n 的二维数组，也是 O(n²)。

这本书的题目 n 一般很小，通常不超过 20，所以开 int a[25][25] 已经很稳。但保险起见，我习惯于开大一点，比如 int a[105][105]，防止题目改数据范围时翻车。另外提醒一下，如果题目允许多组测试数据，每组之间要记得把数组清零，可以用 memset(a, 0, sizeof(a))，否则上一次残留的数据会影响访问判断。

4. 踩坑记录：那些年我们交过的 WA 和 RE

4.1 常见错误速查表

我把这道题里最常见的几类错误整理成了一张表，方便大家对照自查：

其中“矩阵里出现 0”是我见过最多的情况。新手写代码时总喜欢在 for 循环里每次先移动坐标再填数，写着写着就漏掉第一个位置，或者最后一个位置，最后矩阵角落冒出个 0。最好的解决办法就是采用上面推荐的“先填后走”思路，从逻辑上杜绝漏填。

4.2 小数据手工验证法

调试这道题有个很实用的技巧：先用 n=1、2、3 这样的小数据测试。小数据肉眼就能判断对不对，不用盯着 20×20 的矩阵找 bug。

• n=1 时，输出就是：1
• n=2 时，期望输出是：

code复制1 2
3 4

• n=3 时，期望输出是：

code复制1 2 6
3 5 7
4 8 9

我让学生验证时，一定会让他们先跑 n=3。如果 n=3 的输出和样例一致，n=4、n=5 大概率也没问题；如果 n=3 就出错，矩阵才 9 个数，手工都能看出蛇形路径到底断在哪里。最怕的就是一上来跑 n=20，几百个数全是数字，人眼根本看不出哪一步错了。

4.3 调试输出的妙用

有时小数据测试也通过不了，但肉眼又看不出问题，这时候不要干瞪眼，直接在循环里加一行调试输出，把每一步的位置和方向都打印出来：

cpp复制// 调试用，提交前删掉
cerr << "cnt=" << cnt << " x=" << x << " y=" << y << " dir=" << dir << endl;

建议用 cerr 而不是 cout，因为 cerr 不会被 OJ 的答案比较捕获，提交时忘了删也不会影响答案数据。调试输出能清楚地告诉你蛇走到哪一步开始不听话了。比如某一步坐标变成 (0, 3)，那一定是边界修正出了错；某一步坐标跳到 0，说明循环里访问了未初始化的格子。

4.4 输出格式也是分

很多同学代码逻辑对了，却因为输出格式被扣分，非常可惜。题目要求每个数之间用一个空格分隔，行末不能有多余空格，每行结束要换行。如果用的还是老式写法，在循环里每次输出 a[i][j] << " "，行末就会多一个空格，OJ 可能判 Presentation Error 甚至 WA。

推荐用条件表达式处理：cout << a[i][j] << (j == n ? '\n' : ' ')。这一行代码同时解决空格和换行问题，简洁又安全。

5. 变式与延伸：一套思路吃透所有填数题

5.1 螺旋填数：同一套“预判-转向”逻辑

蛇形填数是最基础的二维数组模拟题之一，但它的思想可以迁移到很多变式上。最典型的就是螺旋填数：从左上角开始，先向右走，撞到边界或已填过的格子就右转，一直转到填满整个矩阵。

思路和蛇形填数完全一致，只是方向从两个变成四个。方向数组在这里才真正展现出优势：

cpp复制int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int x = 1, y = 1, dir = 0;
for (int cnt = 1; cnt <= n * n; ++cnt) {
    a[x][y] = cnt;

    int nx = x + dx[dir];
    int ny = y + dy[dir];

    if (nx < 1 || nx > n || ny < 1 || ny > n || a[nx][ny] != 0) {
        dir = (dir + 1) % 4;   // 撞墙就右转
        nx = x + dx[dir];
        ny = y + dy[dir];
    }

    x = nx;
    y = ny;
}

核心在于每次前进前先“试探”下一步的位置，如果越界或者撞到已经填过的数字，就换下一个方向。对比蛇形填数，你会发现它们解决问题的骨架是一样的：记录状态、试探移动、处理边界、切换方向。学会了蛇形填数，再学螺旋填数基本就是一晚上加几个练习题的事。

5.2 反向蛇形与任意起点

蛇形填数还可以变出很多花样，比如从右上角开始向左下填，或者从矩阵中心开始向外填。处理方式都很相似，只需要调整起点和方向定义。

比如从右上角 (1, n) 开始，方向先向左下，撞墙后换右上，整个判断逻辑和原来完全对称，只要把方向数组里的正负号换一下就行。这类变式的意义在于：不要死记硬背某一种边界判断，而是理解“当前方向 + 越界修正 + 方向切换”这个通用流程。方向变、起点变，核心思想不变。

5.3 换个角度看：对角线编号法

最后再提供一个进阶视角，算是从数学层面重新理解这道题。

观察矩阵可以发现，每个格子 (i, j) 的“行号加列号” i+j 恰好是固定的，它决定了这个格子属于哪一条副对角线。从左上角到右下角的方向上，副对角线按 i+j 从 2 到 2n 依次排列。蛇形填数本质上就是按副对角线顺序填充，奇偶条对角线的填充方向相反：奇数条从右上到左下，偶数条从左下到右上，或者反过来。

理论上可以根据这个规律直接计算每个位置的值，甚至不需要数组、直接在循环里按行输出。这种方法代码可能更短，但公式一旦写错就很难排查。竞赛里我更倾向于“稳定优先”，能模拟就模拟，模拟不了再去推公式。理解对角线视角的价值在于，它帮你看到题目背后的规律，下次遇到更复杂的矩阵填充题，多一个思考角度。

我带学生的时候，经常跟他们说：这道题的关键不在背代码，而在把蛇的路径画明白。画图、小数据、调试输出，这三板斧下来，绝大多数问题都能自己解决。等你把蛇形填数和螺旋填数都独立写顺了，二维数组这个坎就算真正迈过去了，后面再遇到什么矩阵旋转、棋盘遍历之类的题，心里都会更有底。