走迷宫最短路径：BFS队列判重与图论模板题全解析

如果你在学算法，或者正在准备机试、笔试，大概率刷过“ACWing 844. 走迷宫”。这道题给一个 n 行 m 列的网格，0 表示可以走的路，1 表示墙，要求从左上角走到右下角，输出最少需要走多少步。一句话概括就是：在二维网格上做 BFS（广度优先搜索），找无权图的最短路径。它看起来只是一道入门的 BFS 模板题，却把队列、判重、状态扩展、最短路径这几件事全部串了起来，很多新手第一次写 BFS 就是在这道题上翻的车。我这篇文章就按自己的思路，把这道题从读题、建模、写代码，到踩坑和扩展，完整讲一遍。适合刚学完基础语法、准备接触图论的人，也适合要打比赛、刷机试的同学拿这道题做一次系统复盘。

1. 题目到底在考什么——先看懂问题的本质

1.1 输入输出与数据范围：先看清这题的约定

题目输入的第一行是两个整数 n 和 m，表示地图有 n 行 m 列。接着是 n 行数据，每行 m 个整数，0 代表空地，1 代表障碍物。起点固定是左上角 (0,0)，终点固定是右下角 (n-1,m-1)。起点和终点保证是 0，也就是可走的空地。输出是一个整数，表示从起点到终点的最短移动步数。

数据范围一般是 1 <= n, m <= 100。也就是说，最多只有 100×100 = 10000 个格子。这个规模非常小，直接 BFS 不会超时，内存也不会爆，属于最基础的算法题级别。但题目越小，细节越经不起马虎，后面很多坑都是这类“小数据”题目里最容易出现的。

还有一点容易被忽略：步数是怎么定义的。从当前格子走到上、下、左、右其中一个相邻格子，算作 1 步。不能斜着走，不能穿墙，不能走出地图边界。这种“每次移动一个单位距离”的模型，就是典型的无权图，每条边的权重都是 1。正因为权重全是 1，BFS 才能保证第一次到达某个格子时的步数就是最短步数。如果哪天你遇到一个走迷宫题目，每一步消耗的体力不一样，那就不能直接上 BFS，得换 Dijkstra 或者 0-1 BFS，这是后话，第 4 节我会展开说。

1.2 为什么一定是BFS：第一次到达就是最短路径

很多初学者会问：DFS（深度优先搜索）不也能走迷宫吗？为什么这题必须用 BFS？我的回答是：DFS 能走通，但没法保证“最短”。

DFS 的特点是“一条路走到黑”，碰到墙或边界再回头换方向。你用 DFS 搜索一条从起点到终点的路径，找到的第一条路径往往是碰运气，不是最短。除非你把所有路径全部搜一遍，再比较哪个最短，那在数据量大一点的时候会直接炸掉。而且 DFS 如果写成递归，棋盘一大，递归深度一高，还可能爆栈。这不是说 DFS 没用，而是它用错了场景。找“一条可行路径”可以 DFS；找“最短路径”在有边权为 1 的图里，BFS 是更自然的选择。

为什么 BFS 第一次到达终点就一定是最近？你可以想象往平静的水面丢一颗石子，波纹一圈一圈往外扩散。第一圈是最靠近石子的地方，第二圈比第一圈远一步，第三圈再远一步。队列里的元素就像这些波纹的边缘，同一时间点的元素都在同一层。对于无权图来说，所有方向的前进代价都一样，所以波纹扩到的那一层，一定是当前离起点最近的“未访问层”。当终点第一次出现在波纹边缘时，它所处的层数就是起点到终点的最短距离。

下面的表格可以帮你把 BFS 和 DFS 的适用场景看明白：

看懂这个本质，你就能明白为什么 BFS 模板总有“队列 + 判重 + 距离数组”这三件套。队列管扩散顺序，判重管别走回头路，距离数组管每个格子离起点几步。三者配合，最终得到的就是从起点到全图每个格子的最短步数，终点那个格子的值自然就是答案。

2. 核心细节拆解——每个变量、每行代码都不是白写的

2.1 队列、距离数组、方向数组：三样东西各司其职

写 BFS 前先把三样基础数据结构想清楚：队列、距离数组、方向数组。

队列存储的是“当前待扩展的格子坐标”。最直观的写法是用queue<pair<int,int>>，把 (x, y) 作为一个整体入队。这样代码可读性好，逻辑也清楚。如果你追求极致性能，也可以用手写数组模拟队列，这一点我在后面的性能对比小节再聊。

距离数组d[N][N]是这道题最核心的设计。它有两个作用：第一阶段记录每个格子离起点多少步；第二阶段作为“是否访问过”的标记。经典的写法是初始化全为 -1，然后起点d[0][0] = 0。为什么用 -1 而不是用 0 来表示“没访问过”？因为起点本身的步数就是 0，如果 0 同时代表“没访问过”，那起点就会被误判成没走过，等别的格子扩展回起点时，又会被当成新节点处理一次，导致重复入队。用 -1 作为初始值，0、1、2、3 这些非负数都表示“已经访问过且步数为几”，语义干净，代码也顺手。

方向数组是标准套路，四个方向对应上下左右：

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

dx[i]和dy[i]合起来表示一次位移。比如i=0时，(-1, 0)表示向上走一格；i=1时，(1, 0)表示向下走一格；i=2时，(0, -1)表示向左；i=3时，(0, 1)表示向右。方向数组的顺序不会影响正确性，只会影响同层节点的扩展顺序。如果题目不要求输出路径，完全不用在意方向顺序；如果要求“字典序最小路径”，那方向数组的写法就有讲究了。

2.2 入队时判重还是出队时判重：这里藏着能否AC的差异

BFS 模板看起来只有几行，但判重的时机是所有新手最容易搞混的地方。先看一种常见错误写法：节点出队以后，才去标记“访问过”。这种写法会带来什么问题？

假设 A 和 B 两个格子都能走到 C。出队 A 时，发现 C 还没被标记，就把 C 入队。紧接着出队 B 时，又发现 C 还没被标记——因为 C 还没轮到出队，所以标记还没打上——于是 C 又入队一次。队列里的重复节点越多，扩展次数越多，数据一大就容易超时甚至爆内存。正确做法是：在把新节点放入队列之前，就完成“是否已访问”的判断并立刻更新距离数组。

这个细节看上去很小，却是能否一次 AC 的关键。标准姿势是这样的：拿到当前队头的坐标 (x, y)，枚举四个方向得到新坐标 (nx, ny)，先判断是否越界，再判断是否是墙，最后判断d[nx][ny] != -1是否成立。三者都通过，才执行d[nx][ny] = d[x][y] + 1; q.push({nx, ny});。把距离更新和入队绑定在同一个瞬间，就能保证同一个格子永远不会重复出现在队列里。

为什么这样做就能保证最短步数？因为 BFS 的队列天然具有“层序性”。先入队的节点距离更小，后入队的节点距离更大。同一个格子第一次被扩展到时，扩展它的节点所在层数一定是最浅的，所以第一次记录的步数就是最短步数。如果你等到出队时再更新距离，虽然最终答案也有可能是对的，但中间会出现大量重复入队，复杂度从 O(n*m) 恶化到 O(状态数的重复倍数)，在小数据上勉强能过，到大数据就原形毕露。

3. 完整实操——从读题到AC的全过程

3.1 C++完整实现：带注释的代码可直接抄作业

下面是这道题的一份标准 C++ 解法，关键行都有注释。你可以直接复制去提交，但我建议你先读懂每一行，然后再动手自己敲一遍。

#include <bits/stdc++.h> using namespace std; const int N = 110; int n, m; int g[N][N]; // 地图，0 可走，1 是墙 int d[N][N]; // 距离数组，初始化为 -1，表示未访问 int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int bfs() { queue<pair<int, int>> q; memset(d, -1, sizeof d); // 全部标记成未访问 d[0][0] = 0; // 起点距离为 0 q.push({0, 0}); while (q.size()) { auto t = q.front(); q.pop(); int x = t.first; int y = t.second; // 如果已经到达终点，直接返回最短步数 if (x == n - 1 && y == m - 1) { return d[x][y]; } for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; // 1. 越界检查 if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 2. 墙壁检查 if (g[nx][ny] == 1) continue; // 3. 判重检查 if (d[nx][ny] != -1) continue; // 入队前更新距离 d[nx][ny] = d[x][y] + 1; q.push({nx, ny}); } } // 题目保证有解，但如果写成通用代码，这里返回 -1 表示不可达 return -1; } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> g[i][j]; } } cout << bfs() << endl; return 0; }

几个容易懂错的点在代码里已经标注了。我再补充一个细节：memset(d, -1, sizeof d)对 int 数组填 -1 是安全的，因为 -1 的补码是全 1，memset按字节填充后结果正好是 -1。有人会用memset(d, 0, sizeof d)然后额外开一个 visited 数组，那样也能 AC，但代码量更多，不如直接用d数组一个顶俩。

提前返回的问题再说一句。我在代码里加了if (x == n - 1 && y == m - 1) return d[x][y];，意思是扩展到终点立刻结束。不加这一行也会在 BFS 结束后从d[n-1][m-1]读到正确答案，但提前返回能少扩展一些无关节点。这个习惯在更复杂的 BFS 题目里很值钱。

3.2 手动模拟一遍BFS：用题目样例把队列画一遍

光看代码还是不够直观，我建议你跟着我手推一遍样例。以常见的 3×3 输入为例：

3 3 0 0 0 0 1 0 0 0 0

地图长这样：第一行三个 0，第二行中间是墙 1，其余是 0，第三行三个 0。从 (0,0) 走到 (2,2)，因为中间被墙挡住，只能从上面绕或者从下面绕，最短步数是 4。下面我把 BFS 的队列变化一步步列出来。

初始状态：队列为 [(0,0)]，d[0][0]=0。

出队 (0,0)，向四个方向扩展：

• 上：越界，跳过。
• 下：到达 (1,0)，空地且未访问，d[1][0]=1，入队。
• 左：越界，跳过。
• 右：到达 (0,1)，空地且未访问，d[0][1]=1，入队。 此时队列为 [(1,0), (0,1)]。

出队 (1,0)，扩展：

• 上：回到 (0,0)，已访问，跳过。
• 下：到达 (2,0)，空地且未访问，d[2][0]=2，入队。
• 左：越界，跳过。
• 右：到达 (1,1)，是墙，跳过。 队列为 [(0,1), (2,0)]。

出队 (0,1)，扩展：

• 上：越界，跳过。
• 下：到达 (1,1)，墙，跳过。
• 左：回到 (0,0)，已访问，跳过。
• 右：到达 (0,2)，空地且未访问，d[0][2]=2，入队。 队列为 [(2,0), (0,2)]。

出队 (2,0)，扩展：

• 上：回到 (1,0)，已访问，跳过。
• 下：越界，跳过。
• 左：越界，跳过。
• 右：到达 (2,1)，空地且未访问，d[2][1]=3，入队。 队列为 [(0,2), (2,1)]。

出队 (0,2)，扩展：

• 上：越界，跳过。
• 下：到达 (1,2)，空地且未访问，d[1][2]=3，入队。
• 左：回到 (0,1)，已访问，跳过。
• 右：越界，跳过。 队列为 [(2,1), (1,2)]。

出队 (2,1)，扩展：

• 上：到达 (1,1)，墙，跳过。
• 下：越界，跳过。
• 左：回到 (2,0)，已访问，跳过。
• 右：到达 (2,2)，空地且未访问，d[2][2]=4，入队。 队列为 [(1,2), (2,2)]。

此时队列里已经有终点 (2,2)。如果写了提前返回，下一步出队 (1,2) 后就会出队终点并返回 4；即使不提前返回，最终读取d[2][2]也是 4。注意到一个现象：到达终点的路径是 (0,0) → (1,0) → (2,0) → (2,1) → (2,2)，全程 4 步。这个路径不是唯一的，(0,0) → (0,1) → (0,2) → (1,2) → (2,2) 也是 4 步。因为 BFS 只要求最短步数，不要求唯一路径，所以哪条先到都无所谓。

3.3 Python实现：用deque写起来更顺手

如果你主要用 Python 刷题，下面这段代码可以作为参考。核心思路和 C++ 完全一致，只是换了容器和语法。

from collections import deque def bfs(n, m, g): d = [[-1] * m for _ in range(n)] d[0][0] = 0 q = deque() q.append((0, 0)) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] while q: x, y = q.popleft() if x == n - 1 and y == m - 1: return d[x][y] for i in range(4): nx, ny = x + dx[i], y + dy[i] if nx < 0 or nx >= n or ny < 0 or ny >= m: continue if g[nx][ny] == 1: continue if d[nx][ny] != -1: continue d[nx][ny] = d[x][y] + 1 q.append((nx, ny)) return -1 n, m = map(int, input().split()) g = [list(map(int, input().split())) for _ in range(n)] print(bfs(n, m, g))

Python 版本要注意一个性能杀手：不要用 list 模拟队列然后pop(0)，因为pop(0)是 O(n) 操作，会把 BFS 的复杂度拖到 O(n²)。必须用collections.deque，它的popleft()是 O(1)。在 100×100 的网格上，两种写法的差距可能不明显，但一旦数据量变大，list 模拟队列会慢得让你怀疑人生。

无论 C++ 还是 Python，这个算法的时间和空间复杂度都是 O(n*m)。每个格子至多入队一次，入队后检查四个方向，总运算量就是格子数的常数倍，非常稳定。

4. 常见问题与排查技巧实录

4.1 样例能过提交却WA：五个高频翻车点

这道题代码不长，但我见过太多人卡在样例能过、提交 WA 的状态。总结下来，翻车点基本集中在五处。

第一，方向数组写错。最常见的错误是把dx和dy搞反，比如该横向移动时用了纵向偏移，或者四个方向只写了三个。这种错误在网格长宽相等的时候容易被样例掩盖，n 和 m 不相等时就容易出问题。建议把四个方向的偏移量固定默写：{-1,1,0,0}配合{0,0,-1,1}，这样上下左右正好一一对应。

第二，坐标写反。有些同学喜欢用i表示行、j表示列，但在入队、判重的时候一不留神把i和j的位置颠倒了。特别是地图是 n 行 m 列，不是 n 列 m 行时，这类错误尤其隐蔽。我的习惯是变量名直接叫x和y，x表示行，y表示列，代码里从头到尾保持一致。

第三，判重时机不对。这个前面已经强调过，出队时打标记会导致重复入队，数据一大就超时。如果你提交后出现 TLE，优先检查这一步。

第四，数组大小开错。g[N][N]和d[N][N]的 N 要足够大，比如N=110应对最大 100 行列的网格没问题。但有些同学定义N=105，刚好卡着数据上限的边，遇到极端数据就越界了。多开 5 到 10 个单位的空间是竞赛里的基本常识。

第五，起点或终点不可达时没有兜底。ACWing 这题保证起点终点一定是 0，所以不考虑不可达也能过。但如果你把代码挪去其他题目，最好还是保留if (g[0][0] == 1)这样的特判，以及在 BFS 结束后返回-1表示不可达。写通用代码的收益远大于多写几行的成本。

4.2 手写队列还是STL queue：一文讲透性能取舍

这题 n × m 最大 10000，用 STL 的queue完全没压力，我不会劝你上来就手写队列。但很多同学会好奇：为什么有的题解用手写数组模拟队列，是不是 STL 太慢？

我先给结论：在 10⁵ 级别以上的状态数时，STL 队列的封装开销会变得不可忽略；但在 10⁴ 级别，两者差异微乎其微。手写队列的核心好处有两个：一是省掉动态内存分配和模板封装的开销；二是能通过头尾下标直接访问队列中的任意元素，方便 debug 时打印整个队列。

手写队列的固定写法如下：

int qx[N * N], qy[N * N]; int head = 0, tail = 0; // 起点入队 qx[tail] = 0; qy[tail] = 0; tail++; while (head < tail) { int x = qx[head]; int y = qy[head]; head++; // 扩展四方向，逻辑与 STL 版本相同 // 入队时：qx[tail] = nx; qy[tail] = ny; tail++; }

队列容量为什么N*N就够？因为每个格子最多入队一次，队列中的元素总数不会超过格子数 n×m。这里开N*N是绝对安全的。要注意head负责出队方向，tail负责入队方向，当head == tail时队列为空，不能再取队头元素。

我自己的建议是：初学阶段优先用 STLqueue，因为它可读性好，你只需要把精力集中在 BFS 逻辑上。等刷题量上来以后，再练习手写队列，慢慢体会两者的性能差异。不要在一道 100×100 的简单题上过早优化，真正的性能瓶颈通常不在这里。

4.3 还能怎么扩展：输出路径、多源BFS与0-1 BFS

很多同学做完这道题就结束了，但我建议你再往前走一步。最直接的扩展是“输出最短路径”。你只需要在 BFS 入队新节点时，额外记录每个节点是从哪个节点扩展来的，用一个前驱数组存起来：

int prex[N][N], prey[N][N]; // 当 (nx,ny) 通过 (x,y) 扩展且未被访问时： prex[nx][ny] = x; prey[nx][ny] = y;

到达终点后，从终点开始不断找前驱，一直到起点，再把路径逆序输出即可。这个扩展在“机器人找路”“迷宫寻宝”这类题目里经常出现，掌握了前驱数组，那些题目能直接套用。

再往外扩一层，就是 BFS 的各种变体。如果地图里有多个起点，要求所有格子到最近起点的距离，那就是多源 BFS，做法是初始化时把所有起点都入队，距离都设为 0，然后统一 BFS。如果地图里有一些传送门或者单行道，状态就可能需要压缩成“坐标 + 钥匙集合”的形式，这是状态压缩 BFS 的范畴。如果不同格子的移动代价不同，普通 BFS 就不适用了，得用 Dijkstra；如果代价只有 0 和 1 两种，还可以用 0-1 BFS，用双端队列代替普通队列。这些进阶内容都建立在今天这个基础模板之上。

所以我经常说，一道好的模板题不只是一道题，它是一个知识原点。你把 844 题嚼碎了，后面很多题学起来都会快。踩过几次坑之后，我真实的感受是：不要急着背模板，先把队列的进出过程在纸上画一遍，比抄十遍代码都有用。

如果你现在刚好刷到这道题，并且觉得“看懂了但写不出来”，那很正常。写不出来说明动手太少，把代码关掉，自己从零开始写，卡住了再看题解。写完之后再把样例手动模拟一遍，你会发现 BFS 不再是抽象的概念，而是一套你真正掌握了的工具。