很多初学信息学奥赛的朋友在“一本通”的二维数组章节里都会撞上一个叫“蛇形填数”的例题。题号我印象很深3365第63章第一个例子。这题不是说有多难而是它那种“走一步看一步”的思路和前面那些“按行列填表”的题完全不是一个套路。哪怕代码基础不错的人第一次写也容易绕进去不是越界就是死循环。这其实是一道非常好的思维训练题过了这一关你对数组下标的掌控力会上一个台阶。这篇东西我不会只贴一份代码然后让你抄。我想把题面拆开把方向数组的原理讲透把几种常见写法的优劣摆出来再把新手容易踩的坑按我实测的顺序列一列。你跟着走一遍应该能彻底拿捏这道题。1. 先看清题面这不是玩蛇是走格子1.1 题面到底要求输出什么题目描述看起来特别简单输入一个整数 n输出一个 n 行 n 列的方阵。方阵里的数从 1 开始按顺时针方向依次递增走出来的路线像一个回字形。举个例子n 4 时输出应该是1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7注意看1 在最左上角然后向右走到头变成 2、3、4接着向下走到右下角5、6、7再向左走到左下角8、9、10然后向上走11、12…… 走到 13 的位置时上面已经是 1 了没路了于是再向右拐填 13、14、15、16。整个过程就是一个顺时针绕圈越绕越往里直到 n×n 个格子全部填满。很多人第一次看到这个输出会以为有数学规律比如每行首尾之间有什么等差关系。实际上你很难找到一个统一的通项公式去算每个位置上的值。它本质上是一个“模拟走路”的问题每一步往下个格子里填数字数字是连续的所以从 1 到 n×n 一共要走 n×n 步。这道题在一本通里被放在编程启蒙阶段却能让不少人卡住原因就是它考察的不是“你会不会用循环往数组里填数”而是“你会不会让程序自己判断什么时候该转弯”。这是从静态填表到动态走位的一个分水岭。1.2 这道题真正考察的点在哪先盘点一下它用到的知识点其实就三样二维数组、循环、边界判断。单看每一项都不难但组合起来就有点意思了。二维数组用来存格子里的数循环用来控制走的总步数边界判断用来决定方向什么时候换。我觉得它真正想让你学会的是“状态”这个概念。程序每走一步脑子里得清楚三件事当前在第几行、第几列面朝哪个方向。方向变了位置也得跟着变位置撞墙了方向才允许变。这个“方向 位置”的联合状态是很多复杂算法的基础。像后面的迷宫问题、BFS、DFS说白了都是在管理类似的状态。所以我不建议一上来就照着网上的代码抄。先把“人是怎么填这个方阵的”转化为“程序每步该做什么”这个思路打通了写代码就是几十分钟的事。2. 从“人的思路”到“机器的思路”2.1 按圈填数 vs 模拟走路面对蛇形填数新手脑子里第一个冒出来的方案往往是“一层一层剥洋葱”先填最外圈再填第二圈再填第三圈。思路没问题用四个 while 循环每圈分别向右、向下、向左、向上填一条边也能做出正确答案。但我个人不太推荐这个思路作为首选原因有两个。第一按圈填的时候每圈的起点和长度都在变化你得维护四个边界变量上边界、下边界、左边界、右边界。每一圈结束之后边界往里缩一圈。光是想清楚这几个边界的更新顺序就已经够绕了。第二当 n 是奇数时最后一圈只有一个格子按圈写法很容易把单个格子重复填两次或者漏掉。模拟走路的思路就干净多了我不管第几圈我只管当前站在哪个格子上下一步能不能走。能走就走不能走就右转右转后肯定能走。这个逻辑对 n 的所有取值都成立代码量也少不容易漏边界。所以我的结论是蛇形填数别去想数学公式也别一开始就按圈写就老老实实用一个“小人”在格子上走。走不通了转个身仅此而已。2.2 方向数组用 4×2 的小表格代替四个循环模拟走路的核心是一个叫“方向数组”的小技巧。我先把代码摆出来再解释它为什么好用。int dx[4] {0, 1, 0, -1}; int dy[4] {1, 0, -1, 0};这 4 行代码表示四个方向向量第 0 个方向是 (dx[0], dy[0]) (0, 1)意思是行坐标不变、列坐标加 1对应“向右”。第 1 个方向是 (1, 0)行坐标加 1、列不变对应“向下”。第 2 个方向是 (0, -1)对应“向左”。第 3 个方向是 (-1, 0)对应“向上”。为什么要用一个数组存方向因为我们不仅要“走”还要“转弯”。转弯就是方向序号加 1四个方向走完一轮再回到第 0 个所以取模就行dir (dir 1) % 4;这个写法有一个巨大的好处代码里不会出现四个几乎一模一样的 for 循环块。你只需要写一份“走一步”的逻辑方向值一变自然就换了个朝向。以后要是题目改成逆时针绕圈我只需要调整 dx、dy 数组里的排列顺序其他代码一行都不用改。这种“把变化的东西参数化”的思维在竞赛里非常值钱。2.3 “撞墙”与“回头”的边界逻辑光有方向数组还不够程序还得知道什么时候该转弯。转弯的条件有两个满足任意一个就得右转下一步走出了矩阵的边界比如行坐标小于 0或者大于等于 n下一步要跳到的格子里已经有数字了说明那是已经走过的路。转换成代码就是这样int nx x dx[dir]; int 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]; }这里面有个细节容易被忽略当你发现当前方向走不通改变了 dir 之后必须立刻重新计算 nx 和 ny。我见过太多人改成 dir 后直接拿旧的 nx、ny 继续走结果下一步还是老位置直接死循环。变量名也容易混淆建议区分“当前位置 x,y”和“试探位置 nx,ny”这个习惯能帮你省下大量调试时间。还有一个细节转弯之后一定能走吗只要当前格子不是被团团围住的死角右转后的方向一定是可行的。因为我们的路径是贴着已填区域走的按顺时针方向绕圈右转后的那个格子要么还没填要么就在当前格子的旁边必然是空的。这一点逻辑上可以放心。3. 可复现的参考代码与逐段解读3.1 C 版本信息学奥赛一本通实测可用先给出完整的 C 代码环境就是常用的 Dev-C 或 CodeBlocks包括头文件和标准命名空间。#include iostream #include iomanip using namespace std; int a[105][105]; // 全局数组自动初始化为 0 int main() { int n; cin n; int x 0, y 0; // 起点在左上角 int dir 0; // 初始方向向右 int dx[4] {0, 1, 0, -1}; // 右、下、左、上 int dy[4] {1, 0, -1, 0}; for (int num 1; num n * n; num) { a[x][y] num; int nx x dx[dir]; int 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 (int i 0; i n; i) { for (int j 0; j n; j) { cout setw(3) a[i][j]; } cout endl; } return 0; }这段代码有几个地方我单独说明一下。第一数组 a 开在 main 外面作为全局变量。全局变量有一个天然的好处所有元素默认都是 0。而蛇形填数判断“这个格子走没走过”恰好可以用 0 表示“没走过”。如果你把数组开在 main 里面局部变量的初值是不确定的必须手动 memset 清空。很多新手在这上面翻车数组里面全是乱七八糟的随机数结果一判断 a[nx][ny] ! 0所有格子都像被走过一样程序第二格就卡死了。第二for 循环从 num 1 到 n * n 结束一共执行 n×n 次。每次给当前位置 a[x][y] 赋一个数然后试探下一步。最后一次循环结束之后x、y 其实已经算到了矩阵外面但那没关系因为循环已经结束了不会再用这个越界位置做任何事。这是这个写法的一个小瑕疵但对结果没有任何影响。第三输出用的 setw(3)作用是让每个数都占 3 个字符宽度默认右对齐。这刚好符合一本通上“每个数占 3 格”的输出要求。如果你不想用 setw写成 printf(%3d, a[i][j]) 也一样。3.2 Python 版本调试和追走位更直观很多刚接触竞赛的孩子还不太熟 C或者想先在本地把思路验证一遍那么用 Python 写一版就很舒服。Python 的代码逻辑和 C 几乎完全一致只是语法上更宽松可以少写很多符号。n int(input()) a [[0] * n for _ in range(n)] x, y 0, 0 direction 0 dx [0, 1, 0, -1] dy [1, 0, -1, 0] for num in range(1, n * n 1): a[x][y] num nx x dx[direction] ny y dy[direction] if nx 0 or nx n or ny 0 or ny n or a[nx][ny] ! 0: direction (direction 1) % 4 nx x dx[direction] ny y dy[direction] x, y nx, ny for row in a: for val in row: print(f{val:3d}, end) print()Python 写法里最需要注意的就是二维数组的初始化。[[0] * n for _ in range(n)]这个写法没问题它会为每一行单独创建一个列表。如果你偷懒写成[[0] * n] * n看起来差不多实际上每一行都是对同一个列表的引用后续填一个数会整列一起变。这个坑我见人踩过太多次改起来倒是容易但排查的过程非常折磨。用 Python 调试还有一个好处就是你可以随时在 for 循环里加一句print(x, y, direction)看小人走到了哪。C 里这么打印也行但每次编译运行都要重新来一遍Python 的修改成本低很多。3.3 输出对齐的三种写法这题输出格式要求很严数位不齐就算格式错误。我见过有人用 cout a[i][j] 输出出来是左对齐的和题目给的样例对不上硬生生丢分。三种常用的对齐写法给你列一下写法示例特点cout setwcout setw(3) a[i][j];C 风格需要 includeiomanip默认右对齐printfprintf(%3d, a[i][j]);C 风格%3d表示占 3 位右对齐简洁直接Python f-stringprint(f{val:3d}, end)Python 3.6 可用3d前面加冒号就是占 3 位右对齐要注意的是setw(3)只对紧接着的一个输出生效不是对整个流一直生效。如果你连续输出多个数字每个数字前都要重新写一次 setw。这是和 printf 差异最大的地方。4. 新手最容易踩的 5 个坑含排查实录4.1 死循环转向后忘了更新位置我先说症状程序运行后没有任何输出CPU 占用率直接拉满看起来像死机了。最常见的死循环原因就是if 里面判断出需要转向也改了 direction但没有重新计算 nx 和 ny。打个比方你站在路口发现前面是墙你脑袋转了 90 度但是脚没动。下一次循环仍然用旧坐标去试探还是那堵墙又转 90 度脚还是不动。循环一直在原地转圈永远填不出下一个数字。解决方式就是在改 direction 之后立刻补上两行nx x dx[dir]; ny y dy[dir];写代码的时候把这两行放在 if 块里边别放在外面。如果你把 nx、ny 的赋值放在 if 外面那改完 direction 也不会生效。4.2 数组不初始化的灵异事件症状也很典型程序没有越界逻辑看着也没毛病但填出来的数乱跑或者到某个位置突然提前转弯矩阵里出现大片 0。原因是局部数组没有清零。C 里如果你在 main 函数里写int a[105][105];它的初始值是不确定的有些编译器里是 0有些里是随机数。这个随机性特别坑人——在本机编译一次能跑换台机器结果就变了。我有一次帮学生查问题代码逻辑从里到外看了三遍找不出毛病最后把他的数组从 main 里面挪到全局问题瞬间消失。从那以后我只要写竞赛代码数组一律开全局。不仅是为了省那几毫秒的初始化时间更重要的是全局数组的默认 0 值永远不会让我踩这个雷。4.3 下标从 0 还是从 1 开始一本通很多例题喜欢用 1 到 n 的坐标让人感觉更符合数学习惯。但方向数组那套写法用 0 到 n-1 会更顺手因为数组的下标天然从 0 开始。如果你混合使用比如起点写x 1, y 1而数组大小只开了 n那么填到 n-1 行的时候就会越界。因为第 n 个格子的下标其实是 n-1不是 n。我觉得最稳妥的方案是全程使用 0 下标边界判断统一写nx n不要额外减 1。这个约定一旦定下来后面所有变体题都遵着走省心。4.4 只有一个格子时的边界情况不要笑这个真的会有人错。当 n 1 时矩阵只有一个格子那输出就一个 1。按照代码逻辑初始位置 (0, 0) 填 1然后试探 nx 1越界转向再试探还是越界然后循环结束。虽然最后 x、y 越界但不影响输出答案是对的。但如果你是先填数、再走、再填数那种写法比如 while 循环里每次先判断能不能走再填数就有可能在 n1 时直接跳过填数步骤。所以我建议用刚才那种“先填数、再试探、再移动”的结构天然支持 n1。4.5 多组数据输入时的数组残留问题有些题会搞多组输入比如 while (cin n) 处理多次查询。第一次运行没问题第二次运行就各种乱。原因很简单上一次填的数据还残留在数组里a[nx][ny] ! 0 的判断把老数据当成“已经走过的路”新路径还没开始就被挡了一半。如果是全局数组每次 while 循环开始前得手动清零可以这样写memset(a, 0, sizeof(a));前提是 includecstring。或者更省事定义数组后每轮只用前 n×n 个格子但 memset 一行的成本完全没必要省。5. 把这道题吃透三种常见变体与举一反三5.1 从右上角起飞的蛇形一本通里蛇形填数其实有多个版本其中不少是从右上角开始先向下走的。比如 n4 时是4 3 2 1 5 14 13 12 6 15 16 11 7 8 9 10这种变体对已经写通左上角版本的人来说改造只需要动两个地方起点坐标变成x 0, y n - 1初始方向从“向右”改成“向下”。方向数组顺序不用动还是右、下、左、上因为整体绕圈方向依然是顺时针。有些同学会把方向数组的顺序改来改去其实没必要。你只需要改变方向和起点让小人从不同的位置、朝不同的方向迈出第一步后续的转弯逻辑会自然适应。这也是方向数组写得通用的好处。5.2 按层剥洋葱的“多层填数”虽然我建议第一版用方向数组但面试和常规教学里按层填也很常见因为它更直观也方便扩展成“输出螺旋矩阵”一类题目。我把思路给出来你可以在纸上画一画。维护四个边界up、down、left、right初始值分别对应 0、n-1、0、n-1。每次循环从 (up, left) 向右填到 (up, right)然后 up 加 1从 (up, right) 向下填到 (down, right)然后 right 减 1从 (down, right) 向左填到 (down, left)然后 down 减 1从 (down, left) 向上填到 (up, left)然后 left 加 1。难点是每填一条边之前要判断上下边界是否已经交叉否则奇数 n 的最后一圈会重复填。写成代码比方向数组啰嗦不少逻辑却能让你对矩阵边界的理解更深刻。建议你先写通方向数组版再回来试这个版本一举两得。5.3 从中心向外绕圈的进阶玩法上面所有的绕法都是从外往里绕还有一种反过来数字从中心开始向外填。配合方向数组写法上只改两处起点改成中心步长变成递增规律。常见中心起点是n / 2如果 n 是奇数中心就一个格子从它开始。n 是偶数时中心其实是 2×2 的格子起点通常取左上角那个。步长规律是右 1 步、下 1 步、左 2 步、上 2 步、右 3 步、下 3 步……每次连续走两步、两步、三步、三步这样递推。实话实说这个变体的难度就上来了不推荐刚学的人去啃。但如果你把蛇形填数本身写完了觉得不过瘾倒是可以用它来检验一下自己有没有真正吃透“方向数组 边界判断”这套组合拳。我当时能把这题独立写出来是在第 N 次调试、每次打印小人位置以后才彻底理解的。那种“突然开窍”的感觉其实就是你脑子里已经把“当前位置、当前方向、下一步试探”这三个变量彻底绑在了一起。这道蛇形填数看似只是二维数组的一道基础题但它教你的一件事特别重要写代码前先在纸上把路线画出来。画完之后程序的骨架就已经定了。剩下的不过是用代码表达你脑中的那幅图而已。