企业官网建设流程全解析

第一次刷到某算法平台的 844 题《走迷宫》时，我承认自己一开始是带着“这题我会”的心态去看的。一个 n 行 m 列的迷宫，0 能走，1 是墙，从左上角到右下角，求最少移动次数。看起来就是标准的搜索题，甚至第一反应是：写个 DFS 不就行了，遇到墙就回头，总能走通。直到我真正交上去才发现，深搜在这道题上不仅慢，而且思路根本就是错的。这道题真正的核心不是“能不能走到”，而是“怎么证明第一次找到的路就是最短的”。今天想用这篇文章，把这道题从原理到代码、再到各种离谱的坑，一次讲透。

1. 为什么这道题必须用 BFS：把迷宫当成一层层扩散的水波

1.1 题面里藏着两个决定算法选型的关键信息

先看题目的两个约束条件：第一，每次只能向上、下、左、右移动一格；第二，求的是从左上角到右下角的“最少移动次数”。把这两条放在一起，就是一个非常典型的“无权图最短路”问题。

什么叫无权图？就是移动任何一步的代价都是 1，不管是从平地走到平地，还是从墙边绕过去，每走一步都只花费 1。在这个前提下，BFS（广度优先搜索）有一个极其重要的性质：它第一次扩展到某个点时，经过的步数一定是从起点到这个点的最短步数。这个性质不是碰巧成立，而是因为 BFS 的扩展顺序本身就是从近到远的，队列里先入队的点一定是距离起点更近的点，后入队的点一定更远。

很多人可能会想：那 Dijkstra 呢？Dijkstra 是处理边权不同的情况。当所有边权都是 1 时，BFS 就是最合适的工具，连优先队列都用不上，一个普通队列就够了。这一点是这道题能沿用模板的基础。

如果把迷宫看成一张由格子组成的图，每个格子是一个节点，相邻的可走格子之间有一条边。那么求最少移动次数，就是在求从起点的格子到终点的格子的最短路。而 BFS 在这个场景下，就像往水池里扔一颗石子，波纹一圈一圈向外扩散，每一圈代表“走了一步能到的位置”。当波纹第一次碰到终点那个格子时，这一圈的半径就是最短距离。

1.2 DFS 为什么天然不适合这道题

许多人（包括当初的我）会本能地选择 DFS：从一个格子出发，递归地向四个方向尝试，走到死胡同就回溯，最后在递归出口去更新一个全局变量 ans，表示当前路径的步数。这种方法在逻辑上确实能找到一条路径，实际上也能找到最短路径，只要把所有路径都枚举一遍再取最小值。问题是，这个“把所有路径都枚举一遍”的做法，在最坏情况下会把简单的二维迷宫跑成一个指数级的灾难。

在 n 和 m 都取到 100 的迷宫里，从左上角到右下角的合法路径数量会多得惊人。每一格可能有多条岔路，DFS 需要一条一条试。即使加了“当前步数已经大于当前最优解就剪枝”的优化，迷宫里的路径仍然可能大量存在，递归深度也有机会逼近 200，运行时间完全不可控。我见过有人在 n=m=20 的小地图上用 DFS 跑出了十几秒的耗时，更不用说 100×100 的规模了。

从本质上讲，DFS 擅长的是“判断是否存在一条路径”，以及“枚举所有可能的方案”。而 BFS 擅长的是“在单位代价条件下寻找最短路径”。它们两个的分工完全不同，用 DFS 强行去求最短路，就像用一把锤子去拧螺丝，虽然也能拧进去一点，但效率和正确性都没法保证。

为了更直观地对比，我把两种思路的区别列了一下：

2. BFS 求最短路的三个关键装备：队列、方向数组、距离表

2.1 队列：下一层的“待办事项清单”

BFS 的核心数据结构是一个队列，队列里存放的是“当前这一层已经到达、但还没有继续向外扩展的点”。初始状态下，把起点放进队列。然后进入一个循环：从队头取出一个点，看看它的上下左右四个方向能走到哪里，能走到的点如果还没有被访问过，就把它放到队尾。

队列的先进先出性质，在这里起着至关重要的作用。假设当前队列里有两个点 A 和 B，都是走 2 步能到达的点，它们入队的顺序是 A 先、B 后。那么下一次取出的点一定是 A，由 A 扩展出来的点是走 3 步能到达的点，会被排在 B 的后面。这样一来，整个搜索过程就严格按照“距离起点远近”的顺序一层层推进，不会出现某条很长的路径抢在很多短路径之前把终点标记掉的情况。

如果这里不用队列而用栈，也就是改成深度优先的顺序，那么当一个点被第一次标记访问时，它不一定是距离起点最近的那个点，后面再用它去更新其他点，得到的结果就可能不是最短距离。所以 BFS 保证最短路的前提，就是“必须用队列”。

2.2 距离表：既是访问标记，又是最终答案

BFS 的第二个关键组件是一个和迷宫等大的距离数组，我习惯记作d[x][y]，它表示从起点走到坐标(x,y)的最短步数。在代码里，这个数组初始化时统一设为 -1，同时把起点的距离设为 0。

这里有一个初学者很容易纠结的问题：为什么初始值要选 -1，而不是 0？因为 0 本身是一个有效的距离值，起点就是 0，如果所有点初始都设为 0，就没办法区分“这个点还没走”和“这个点距离为 0”。把距离数组初始化为 -1 之后，判断一个点是否访问过，只需要看d[x][y] == -1还是不等于 -1 就行了，一次判断同时完成了“访问标记”和“距离记录”两件事。

当从当前点(x,y)扩展到一个新点(nx,ny)时，如果能走且没访问过，就执行d[nx][ny] = d[x][y] + 1。因为 BFS 的特殊性，这个赋值只会发生一次，之后不需要再做任何“如果发现更短路径就更新”的操作。这点和 Dijkstra 不同，Dijkstra 需要用if (d[to] > d[cur] + w)反复松弛，而 BFS 在单位边权下不需要松弛。如果你看到有人在这道题里写了一大堆比较更新的逻辑，那大概率是把问题复杂化了。

2.3 方向数组：上下左右到底怎么表示

第三个部分我已经习惯固定写法：定义两个数组dx和dy，分别对应四个方向在 x 轴和 y 轴上的偏移量。

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

这个写法对应的方向依次是：上、右、下、左。用(dx[i], dy[i])去和当前位置相加，就能得到邻居坐标。例如当前位置是(x, y)，当i=0时，新的坐标是(x-1, y)，即上方的格子；当i=1时，新的坐标是(x, y+1)，即右侧的格子。

方向数组看起来简单，但它最大的坑在于配对。如果dx和dy没有一一对应好，比如dx[2]=1但dy[2]=1，那就意味着这个方向是向右下角斜着走，这在迷宫里是不允许的。所以我建议不要在代码里临时改方向数组的顺序，而是固定一套写法，然后在需要覆盖八个方向（八连通）时再去额外扩展成dx[8]和dy[8]，而不是在四个方向里折腾。

3. 完整可 AC 的代码与逐段拆解

3.1 先放整段代码，再解释为什么这样写

下面这份代码我按下标从 1 开始的方式处理，迷宫的第 1 行到第 n 行、第 1 列到第 m 列对应题目里的坐标。很多题解也喜欢从 0 开始，但两种方式的原理完全相同，关键是边界条件要对应上。

#include <iostream> #include <cstring> #include <queue> using namespace std; const int N = 110; int n, m; int g[N][N]; // 迷宫地图，0 表示可走，1 表示墙 int d[N][N]; // 距离数组，初始化为 -1 int bfs() { memset(d, -1, sizeof d); queue<pair<int, int>> q; d[1][1] = 0; // 起点到自身的距离为 0 q.push({1, 1}); // 起点入队 int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; while (q.size()) { auto t = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int x = t.first + dx[i]; int y = t.second + dy[i]; // 越界剪掉 if (x < 1 || x > n || y < 1 || y > m) continue; // 撞墙剪掉 if (g[x][y] == 1) continue; // 访问过剪掉 if (d[x][y] != -1) continue; d[x][y] = d[t.first][t.second] + 1; q.push({x, y}); } } return d[n][m]; } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> g[i][j]; } } cout << bfs() << endl; return 0; }

这段代码的核心逻辑全在bfs()函数里，主函数只是负责读入地图然后调用。接下来我拆开说几个容易忽略的点。

3.2 为什么起点距离要单独设置成 0，而不是在循环里处理

很多人会想：能不能让队列从起点开始，然后每次扩展时再判断起点？可以，但会很别扭。起点的距离是 0，这是一个基准值，如果不在入队前设置好，后续的d[x][y] = d[t.first][t.second] + 1就没有办法计算，因为d[t.first][t.second]还是 -1，加 1 变成了 0，整个距离就全乱了。

起点先入队这个动作，相当于给 BFS 提供了一个“第一层种子”。然后每一轮从队头取出一个点，去生成它的下一层邻居。如果把整个迷宫看成一棵从起点向外生长的树，起点就是根节点，d[1][1]=0就是根节点的层号。

还有一个小细节：这里返回的是d[n][m]，也就是终点坐标对应的距离。因为起点距离设为 0，所以这个值就是题目要求的“最少移动次数”。但注意，如果题目换了一种问法，问“经过多少个格子”或者“走了多少步到达终点”，答案可能需要在d[n][m]的基础上加 1。这种细节一定要看题目的原文描述，不能在模板上死记。

3.3 三个 continue 条件的顺序值得讲究

在扩展邻居时，我写了三个连续的continue：越界、撞墙、已访问。这个顺序不是随意的，而是尽量把最廉价的判断放在前面。

越界判断最快，只是比较四个大小关系，不需要访问数组，所以放在第一位。撞墙需要访问g数组，放在第二位。已访问判断需要访问d数组，同时它在逻辑上依赖于前面的判断都通过，所以放在最后。当然，这三个判断调换顺序在正确性上不会有什么影响，因为它们是互相独立的条件，任何一个不满足都意味着这个邻居不能走。但养成“先判越界，再判障碍，最后判访问”的习惯之后，写更复杂的图论搜索时不容易漏条件。

4. 我在这道题上踩过的坑和最终的排查思路

4.1 用 DFS 交上去，换来一发 TLE

我第一次做这道题时，写的不是 BFS，而是 DFS。当时的想法非常直白：定义一个递归函数dfs(x, y, step)，四个方向尝试，能走就走，走到终点就用ans = min(ans, step)更新答案。在小样例上测试，结果完全正确，我甚至觉得自己已经做完了。

结果一交上去，超时的红色提示直接教做人。后来我意识到，这道题的数据范围是 100×100，DFS 枚举路径时，有很多段路径在到达终点之前就不断在若干条岔路之间来回试探，递归层数接近 200，运行时间根本不是 (O(n \times m)) 能比的。我在本地试着用一个稍大一点的随机迷宫跑，程序像卡死了一样长时间不出结果。从那以后我再也没有在“求最少步数”的问题上用过 DFS 作为首选方案。

4.2 队列越扩越大：忘了标记访问导致死循环

还有一次，我写 BFS 的时候只判断了“地图能不能走”，忘了判断“这个点是不是已经访问过”。结果队列里反复出现同一个点，程序在一张非常小的地图上也能跑出几十万次循环，最后因为队列占用内存太大，直接报错退出。

这个坑的本质是：迷宫是存在环路的，一个格子可以通过不同的路径多次到达。如果不标记访问，BFS 就丧失了对“哪些点已经处理过”的记忆，陷入无限重复。排查的时候我用了最笨也最有效的办法：在每个点出队时打印(x, y)和d[x][y]，肉眼看到同一个坐标出现了很多次，立刻就明白了。这个检查方法现在依然是我调 BFS 相关问题的首选手段，与其盲猜，不如直接把搜索轨迹打印出来看。

4.3 方向数组悄悄写错，答案差了一截

方向数组如果写错，通常不会导致死循环，而是会让答案莫名其妙地偏大。我曾经把dx和dy写成：

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

看起来好像还是四个方向，但实际上dx[1]=0, dy[1]=-1是向左，dx[3]=0, dy[3]=1是向右，和原来的“上右下左”少了一个方向，多了一个方向。在迷宫较稀疏时，程序可能绕远路到达终点，答案自然比真实值偏大。

这种错误最难受的地方在于：代码不报错，小样例也可能能过，但是答案错误。我这里给一个实用的自检方法：写完之后，在代码里刻意把四个方向都走一遍，输出所有能到达的邻居坐标，人工核对是否覆盖了上下左右四个方向且没有斜线。核对一次之后，以后就都复制同一套方向数组，不搞创意。

4.4 边界情况：如果终点根本走不到怎么办

题目数据保证了从左上角到右下角一定存在通路，所以我在bfs()函数里可以直接返回d[n][m]，不会出现 -1 的情况。但以后遇到类似题目时，最好留一个心眼：如果题目没有保证可达，应该先判断d[n][m] == -1，再决定输出什么值。

另外，当 n=1、m=1 时，起点就是终点，答案应为 0。我的代码里d[1][1]一开始就设置为 0，while 循环会取出起点尝试四个方向，但所有方向都越界，循环结束，返回d[1][1]也就是 0，逻辑正确，不需要特判。

5. 从这道题延伸出去：BFS 模板的迁移与真正吃透的标准

5.1 如果题目要求输出路径，怎么改造

有些迷宫题不只要输出最短步数，还要输出具体走过的路径。这时候只需要额外开一个和迷宫同样大小的前驱数组pre，记录每个点是“从哪个点走过来的”。

在 BFS 扩展时，当一个新点被更新距离并入队，同时也记录它的前驱：

pre[x][y] = {t.first, t.second};

当 BFS 结束后，从终点(n, m)出发，沿着pre数组不断回退，就能一路回到起点。把这一路上的坐标存进一个数组，最后 reverse 一下，就是从起点到终点的最短路径之一。

这里注意一个细节：前驱数组只在第一次访问到该点时记录，因为第一次访问时的路径已经是最短路径，不需要后续再更新。这和距离数组d的赋值逻辑完全一致。

5.2 把“坐标”扩展成更复杂的状态：BFS 的真正威力

很多初学者做完这道题之后，会觉得 BFS 只能用在二维迷宫里，其实不是。BFS 的核心要素只有一个：状态。状态可以是一个坐标(x, y)，可以是坐标加剩余步数(x, y, rest)，甚至可以是坐标加钥匙集合(x, y, mask)。

比如经典的“带钥匙的迷宫”问题，每一把钥匙对应一个 bitmask，那么状态就变成了(x, y, keys)，其中keys是一个整数，记录当前已经获得了哪些钥匙。BFS 照跑不误，只是从曾经的四个方向扩展，变成了“四个方向加上是否获得新钥匙”的状态转移。第一次到达终点且拥有所有钥匙时，就是最短步数。

从这个角度看，走迷宫这道题真正教会我们的不是怎么移动，而是“如何在状态空间里一层层地扩展，直到找到目标状态”。这为后面理解八数码、隐式图搜索等更抽象的问题打下了基础。

5.3 做到什么程度，才算真正掌握了这道题

我自己的标准是三个层次。

第一层，能独立写出 BFS 的核心代码，不查资料，10 分钟内无 bug 写完。第二层，能用自己的话向别人解释“为什么 BFS 第一次到达终点就是最短距离”，解释包装边权相等、队列先进先出这些前提条件。第三层，能在 BFS 模板上做扩展，比如输出路径、处理多源起点、处理带状态问题，知道在哪里改动、哪里不能动。

如果只做到第一层，那这道题刷完就只是“会抄模板”。做到第二层和第三层，才算真正理解和掌握了搜索的基本功。

我在刷题过程中最大的体会是：算法题里最值钱的不是那个 AC 代码，而是想明白“为什么这样做是对的”的过程。走迷宫这道题虽然简单，但它是理解 BFS 求最短路径原理的最佳切入点。以后遇到更复杂的搜索题，都可以回来想想这层水波扩散的逻辑，很多困惑就会迎刃而解。