企业官网建设流程全解析

矩阵遍历类的题目里，Z字形扫描算是一个很典型的“看着简单，写起来容易翻车”的题。我第一次做它时，心想这不就是两个方向来回走嘛，结果状态机写了二十几行，样例过了，n=4 一跑就卡在右上角出不来，最后居然在调试信息里看到同一个坐标被打印了三次。后来我把整个走法按照坐标一行行列出来，才发现自己一直把“撞墙后的横向调整”和“纵向调整”的顺序搞反了。这篇文章先把Z字形的移动规律拆明白，再给一套稳定模拟的代码，最后介绍一种不模拟、直接按下标规律输出的做法，适合正在备 CSP 这类认证考试的开发者，也适合所有想彻底搞懂矩阵遍历的人。

1. 先把“Z”字走法画在纸上：方向交替的本质

1.1 模拟一遍完整路径，规则就藏在坐标变化里

假设有一个 4×4 矩阵，元素值暂时不看，只看坐标 (x, y)。Z字形的完整路径是：

(0,0) → (0,1) → (1,0) → (2,0) → (1,1) → (0,2) → (0,3) → (1,2) → (2,1) → (3,0) → (3,1) → (2,2) → (1,3) → (2,3) → (3,2) → (3,3)

我建议任何人都不要把这张表背下来，而是观察它背后的运动单位。你会发现，路径里绝大多数步骤是一次斜向移动：要么往右上（x 减 1、y 加 1），要么往左下（x 加 1、y 减 1）。只有某些特殊时刻，路线出现一次水平或垂直的平移：从(1,0)到(2,0)是一次向下平移，从(0,2)到(0,3)是一次向右平移，从(3,0)到(3,1)又是一次向右平移。这些平移不是随意的，它们全部发生在斜线方向已经走不下去、必须换一条新斜线的时候。

换句话说，Z字形可以拆成两个完全对称的循环：先沿右上方向一直走，走到边界就换一条新的斜线，再沿左下方向一直走，走到边界再换。这个规律写进代码就是状态机，画在草稿纸上就是箭头交替。很多教程一上来就贴状态机代码，但我建议你先在纸上画一个 4×4 格子，自己把箭头标一遍。这个操作花不了 30 秒，却能让后面的代码理解难度下降一大半。

画完会发现一个有意思的结论：这个题目根本没有“四条边方向轮流切换”这种复杂规则，它的本质只有两个斜向方向，外加两个用于“换行”的平移动作。理解到这一层，题目就已经解决一半了。

1.2 “撞墙”之后怎么办：两种边界调整规则

斜线走到边界究竟怎么调整，是整道题最核心的细节，也是我最初翻车的地方。我们把两个方向分开看。

先说右上方向（x-1, y+1）。能够继续走的条件是 x-1 >= 0 且 y+1 < n。一旦不满足，说明当前点已经在矩阵的边缘。此时有两种合法调整：如果还能向右（y+1 < n），就向右平移一格；如果右边已经出界（也就是当前点已经贴住最右列），就只能向下平移一格。举个例子，4×4 矩阵里坐标 (0,2) 下一步想要右上会出上边界，但右边还有位置，所以从 (0,2) 平移到 (0,3)。而坐标 (0,3) 右侧已经没有位置，右上更不可能，所以只能向下变成 (1,3)。

这里最容易写错的地方是判断顺序：要先判断“能不能右”，再判断“要不要下”。如果先看 x == 0 就向右平移，在右上角 (0,3) 就会试图执行 y+1=4，直接越界；如果先看 y == 0 就向下平移，也会在特殊位置翻车。正确顺序是：

• 能继续右上：x--, y++。
• 否则：能向右就 y++，不能向右就 x++。

再说左下方向（x+1, y-1），它和右上方向完全对称。能继续走的条件是 x+1 < n 且 y-1 >= 0。受阻后，如果还能向下（x+1 < n），就向下平移一格；如果已经贴住最后一行，就只能向右平移一格。比如 (1,0) 在左下方向会走到 (2,0)，再继续走到 (3,0)，此时还想左下已经出界，但因为当前已经在最后一行，所以向右平移成 (3,1)。注意这里也不要先判断 y == 0 就向下，因为(3,0)的左下角位置再往下已经出界，应该向右。

两个方向合起来，可以概括成一句话：右上受阻，能右则右，不能右则下；左下受阻，能下则下，不能下则右。这句话我后来反复用在同类题目里，比死记一堆边界 if 判断要可靠得多。你甚至可以在草稿纸上只写这一句话，然后照着它写代码。

1.3 为什么要区分奇偶对角线

除了用方向状态机，还可以利用另一个规律：任意一步移动，坐标之和 x+y 在一条斜线内部保持不变，只有切换斜线时才会增加 1。以 4×4 为例，第一条斜线上 x+y=0，只有 (0,0)；第二条斜线 x+y=1，包含 (0,1) 和 (1,0)；第三条斜线 x+y=2，包含 (0,2)、(1,1)、(2,0)，以此类推。

再看具体扫描顺序会发现：x+y 为偶数的斜线，输出顺序是从 x 较大的端点扫向 x 较小的端点，也就是 x 递减方向；x+y 为奇数的斜线，输出顺序正好反过来，是 x 递增方向。这个奇偶规律不是巧合，它正是 Z 字形交替方向的数学表达。如果按照这个规律走，相邻两条斜线之间不需要额外的方向变量，只需要根据当前斜线的编号奇偶决定遍历方向即可。这个结论会直接引出第三部分那种完全不模拟的解法，也是理解整道题最省力的方式。

在这里我要特别提醒一下：不要把“偶数是右上方向、奇数是左下方向”背反。最稳妥的记忆办法是直接拿 x+y=2 这条斜线验算，它包含 (0,2)、(1,1)、(2,0)，扫描顺序是先 (2,0) 再 (1,1) 最后 (0,2)，x 从 2 递减到 0，所以偶数对应 x 递减。只要考试时能想起这一条，规律就不会记错。

2. 模拟解法：从状态机到方向数组，最稳的一版长这样

2.1 状态机版本：两个主方向和四个调整动作

很多解法喜欢用四个方向数组，分别表示右、左下、下、右上。但实际走起来你会发现，右上和左下是“主导方向”，右和下只是“受阻后的平移动作”。把它们混在一起容易把判断条件写复杂。我更推荐用布尔值标记当前主方向，写起来直观，也不容易漏掉角落情况。

下面这份 C++ 代码，是我在考场上会用的版本。它先把 (0,0) 放进答案，之后循环 n*n-1 次，每次先尝试按当前方向斜向走，失败就做平移，并切换方向。

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<vector<int>> a(n, vector<int>(n)); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> a[i][j]; int x = 0, y = 0; bool upRight = true; // true: 当前沿右上方向, false: 当前沿左下方向 vector<int> ans; ans.push_back(a[0][0]); for (int step = 1; step < n * n; ++step) { if (upRight) { if (x - 1 >= 0 && y + 1 < n) { x--, y++; } else { if (y + 1 < n) y++; else x++; upRight = false; } } else { if (x + 1 < n && y - 1 >= 0) { x++, y--; } else { if (x + 1 < n) x++; else y++; upRight = true; } } ans.push_back(a[x][y]); } for (int i = 0; i < (int)ans.size(); ++i) { if (i) cout << ' '; cout << ans[i]; } cout << endl; return 0; }

这段代码为什么可靠？因为每一轮只有一个动作：要么斜向走一格，要么受阻后平移一格。不会有“同时移动两个方向”的机会，坐标自然不会跳。再加上循环次数固定为 nn-1，只要每轮都恰好把当前位置入结果，那么最终答案的元素个数一定是 nn，不会多也不会少。很多翻车写法都是循环写成 n*n 甚至 while(true)，最后要么漏掉最后一个元素，要么越界访问。

有同学可能会问，为什么受阻后只平移一格就马上切换方向？因为平移的一格本身，恰好就是下一条斜线的端点。举个例子，右上方向从 (0,2) 受阻，向右平移到 (0,3)，这个 (0,3) 就是 x+y=3 这条斜线的端点；随后进入左下方向，就可以沿着 x+y=3 这条斜线一路走。如果平移两格或者跳着走，就会漏掉中间的元素。这一条是理解整个状态机逻辑的关键。

2.2 Python 版：同样的逻辑，考场五分钟可写

Python 版本的代码逻辑和 C++ 完全一致，变量名我也刻意保持相同，方便两门语言做对照。

def zscan(n, mat): x = y = 0 up_right = True ans = [mat[0][0]] for step in range(1, n * n): if up_right: if x - 1 >= 0 and y + 1 < n: x -= 1 y += 1 else: if y + 1 < n: y += 1 else: x += 1 up_right = False else: if x + 1 < n and y - 1 >= 0: x += 1 y -= 1 else: if x + 1 < n: x += 1 else: y += 1 up_right = True ans.append(mat[x][y]) return ans n = int(input()) mat = [list(map(int, input().split())) for _ in range(n)] ans = zscan(n, mat) print(' '.join(map(str, ans)))

Python 在认证考试里的优势是写起来快，适合先验证思路。如果题目数据规模比较大，比如 n 到 1000，逐行 input() 可能会比批量读取慢，可以把输入改成一次性读入再分割。不过核心移动逻辑不用改，因为瓶颈在输出规模的 n*n 个元素上，状态机本身是 O(n^2) 时间、O(n^2) 空间（答案数组），这一点对任何语言都一样。

2.3 最容易让循环“卡死”的三个点

我已经见过不少版本的 Z 字形代码，翻车原因高度一致，基本集中在这三个地方：

第一，先切换方向再做边界判断。这是个很自然的错误：有些人觉得“反正走到头就换方向”，于是把 upRight 的取反写在最外层，再根据新方向去移动，结果坐标会在边界处来回横跳。正确的顺序永远是先按当前方向尝试走一步，这一步成功就直接走，失败才处理平移并切换方向。方向切换只发生在“这次移动无法继续”之后，顺序反了就会出现 (0,3) 跳到 (1,3) 又跳回 (0,3) 这类死循环。

第二，受阻后的调整条件写反。右上受阻后应该是“能右则右，不能右则下”，左下受阻后是“能下则下，不能下则右”。我见过有人把左下受阻写成“能右则右，不能右则下”，结果在 (3,1) 这样不是最右列的位置直接越界。这个问题不单靠背代码解决，最好的办法是拿右上角 (0,3) 和左下角 (3,0) 这两个特殊点分别走一遍，看是否落在正确位置。

第三，循环次数和元素个数对不上。我建议把起点单独放进答案，然后循环 n*n-1 次。如果你决定每轮“先输出再移动”，就要额外处理最后一轮移动越界的问题，代码判断会多出一层。在调试时，还可以打印 step 和 len(ans)，发现两者对不上就说明某一步没有成功移动。现场排错时，这两行调试信息比什么都好用。

3. 不撞墙的另一种思路：按对角线直接扫输出

3.1 数学规律：每一条对角线上的坐标满足 x+y=k

模拟法符合直觉，但代码还是有点长。其实这道题还有一个更“数学”的解法：把整个矩阵按照 x+y 的值分成 2n-1 条斜线，第 k 条斜线上的坐标全部满足 x+y=k，其中 k 从 0 取到 2n-2。

对于第 k 条斜线，x 的取值范围需要同时满足两个约束：x 必须在 [0, n-1] 范围内；y = k-x 也必须在 [0, n-1] 范围内。合并起来就是：

lo = max(0, k - (n - 1)) hi = min(k, n - 1)

这个公式看似复杂，实际含义很直白：当 k 比较小、斜线靠近左上角时，x 从 0 开始；当 k 比较大、斜线靠近右下角时，x 的下限被 y <= n-1 约束住。比如 n=4、k=5 时，lo = max(0, 5-3) = 2，hi = min(5, 3) = 3，所以这条斜线只有 (2,3) 和 (3,2) 两个点，完全符合 Z 字形路径上的第 14、15 步。

有了 x 的区间，再根据 k 的奇偶性决定遍历方向，就能直接输出整条斜线。为何用奇偶性？前面说过：偶数 k 对应 x 递减方向，奇数 k 对应 x 递增方向。

3.2 奇偶分开遍历，代码比模拟更短

看一段 C++ 实现，核心只有一个循环加两个内层循环：

vector<int> zscan(int n, vector<vector<int>>& a) { vector<int> ans; for (int k = 0; k < 2 * n - 1; ++k) { int lo = max(0, k - n + 1); int hi = min(k, n - 1); if (k & 1) { // 奇数：x 递增方向，沿左下走 for (int i = lo; i <= hi; ++i) ans.push_back(a[i][k - i]); } else { // 偶数：x 递减方向，沿右上走 for (int i = hi; i >= lo; --i) ans.push_back(a[i][k - i]); } } return ans; }

我刻意把偶数情况放在后面用递减循环，对应“从下端扫向上端”的实际顺序。写这段代码时最容易犯的错误是把奇偶和方向对调，只要拿 k=1 和 k=2 两组数据一验就能发现。k=1 包含 (0,1)、(1,0)，扫描顺序是从 (0,1) 到 (1,0)，这是 x 递增方向；k=2 包含 (2,0)、(1,1)、(0,2)，扫描顺序是从 (2,0) 到 (0,2)，这是 x 递减方向。

这个方案的优点是代码短，几乎没有边界 if 判断，也完全没有“撞墙”概念。缺点是初次接触时不容易想到。建议你把两张图并排画出来：一张是路径箭头图，一张是 k 分区图，看到它们一一对应，这个解法就彻底记住了。

3.3 时间复杂度与正确性分析

从复杂度看，对角线分组法依然是 O(n^2)，因为矩阵有 n*n 个元素，任何解法都要至少输出这么多数字，所以理论上不可能有低于 O(n^2) 的算法。模拟法的每个元素也恰好被访问一次，但每次移动都要比较两个边界条件；对角线法虽然循环层数看起来多，实际上每个元素只执行一次 push_back，常数更小，代码也更不容易出状态类 bug。

空间方面，如果只输出而不保存，对角线法只需要几个 int 变量，是 O(1) 辅助空间；如果像上面代码一样先存答案再输出，辅助空间是 O(n^2)。认证考试通常不卡这个空间，但如果你希望节省，也可以在内层循环里直接 printf，不需要 ans 数组。

正确性上，我建议用 n=4 的路径逐项对照：从 k=0 到 k=6，每条斜线的 lo、hi 分别是 (0,0)、(0,1)、(0,2)、(1,2)、(2,3)、(2,3)、(3,3)，依次输出的元素数量是 1、2、3、4、3、2、1，总和正好是 16。这 2n-1 条斜线的长度本身也呈现对称的“先增后减”，和 Z 字形的自然结构完全吻合。只要这条总长度对得上，就说明没有漏元素。

4. 考场细节与自查清单：把边界用例当成评分点

4.1 输入输出格式：空格和换行别留暗坑

认证题对输出格式的要求，通常是一行内用空格分隔全部元素，不允许额外换行，也不喜欢行尾多空格。最稳妥的办法就是先把结果收集到一个数组里，最后统一打印，打印时用一个 flag 判断当前是否第一个元素，避免行尾出现多余空格。这个技巧我在 C++ 版本里已经用到了，Python 里直接 join 一步搞定。

别看这个细节小，很多人在考场上因为输出格式被扣了冤枉分。判题系统一般不判行尾空格，但不要赌这个；如果输出多了一个换行，或者元素之间用了逗号，那基本就是白送分数。写完代码后，第一件事不是看业务逻辑，而是检查输出语句是否严格符合题面描述。

4.2 边界用例自测：n=1、n=2、n=4

写完代码，我强烈建议至少跑下面三个测试用例。它们分别对应最短路径、方向切换、完整边界三条不同的问题维度。

以 n=3 为例，路径坐标是 (0,0)、(0,1)、(1,0)、(2,0)、(1,1)、(0,2)、(1,2)、(2,1)、(2,2)，对应数字就是 1、2、4、7、5、3、6、8、9。如果你用状态机版本跑出来第 4 个数字不是 7，说明方向没有正确从 (0,1) 切到左下；如果第 6 个数字不是 3，说明右上边界平移逻辑有误。这组用例能把绝大多数状态机问题暴露出来，而且只需肉眼就能核对。

n=4 的用例更全面，它会强迫代码处理右上角、左下角、最右列、最后一行这些特殊位置。务必跑通后再提交，不要拿着样例通过就直接交卷。

4.3 复杂度的快速判断和防超时细节

Z 字形扫描的输出规模就是 n*n，所以复杂度下限已经固定。做题时先看 n 的范围：如果 n 在 1000 左右，O(n^2) 意味着约百万次输出，C++ 完全没问题，Python 也能接受；如果 n 是 10 的 4 次方，那么矩阵本身就有 1 亿个元素，这类认证题一般不会出现，因为这已经不是算法难度，而是 IO 压力了。

真正的超时隐患通常来自不必要的常数开销。C++ 里如果没写 ios::sync_with_stdio(false)，cin 可能变慢；Python 里如果逐行 input() 读取很大的矩阵，也会成为瓶颈。遇到大数据量，我一般建议把所有输入一次性读完再解析，或者用 sys.stdin.buffer.read()。移动逻辑本身别做多余的函数调用，更不要在循环体内用字符串拼接整个答案，那会把 O(n^2) 的复杂度再叠一个 O(n^2) 的拷贝成本。

4.4 调试建议：先画图，再写状态，最后删调试输出

我调试这类模拟题的方法很土但有效：把当前坐标、当前方向输出在每次移动之后，跑 n=4，然后和手动画出来的路径逐项对照。如果发现第 7 步之前就已经偏了，很快就能定位到是哪个方向的判断条件少写了边界。改完逻辑之后，记得把调试输出删除，或者用条件编译包起来。

准备开始写代码之前，我强烈建议先画一个 4×4 格子，用箭头把路径标一遍，然后把“右上受阻能右则右，不能右则下；左下受阻能下则下，不能右则右”这句话写在代码注释顶部。这个顺序不要颠倒，画图花的时间远少于写完一版错误代码再调试的时间。认证考试现场最怕的不是题目难，而是思路没理清就开始敲键盘，Z 字形扫描恰好就是一道“理清思路 > 急着写码”的典型题。

我自己的一个小习惯是：做完 Z 字形扫描，顺手在草稿纸上再把右上角 (0,n-1) 和左下角 (n-1,0) 这两个关键角的动作各写一遍。右上角向右受阻，所以只能向下；左下角向下受阻，所以只能向右。这两个点只要能走对，整个状态机的边界条件基本就稳了。最后再说一遍，三种解法里我平时最常用对角线分组法，因为它连方向变量都不用维护；但第一次做这道题的朋友，我依然建议先用状态机版本建立路径直觉。两种方法都跑通 n=1、n=2、n=3、n=4 四组用例之后，这道题才算真正吃透了。