迷宫最短通道7-39：BFS广度优先搜索实战解析

说到“7-39 求迷宫最短通道”这道题，熟悉数据结构课程设计圈的人应该不陌生。这是我在某高校OJ平台上刷过的一道经典BFS题目，也常被拿来作为“广度优先搜索入门”的面试热身题。天天和栈、队列打交道的同学，第一次看到它时往往会陷入两种误区：要么直接上DFS硬跑，结果发现路径“能通但不够短”；要么卡在读入方式上，坐标和行列反复搞混，还没开始BFS就交了几次WA。

这篇文章我打算一次性把这道题讲透：从题目拆解、图的建模到BFS的核心逻辑，再到方向数组、父节点恢复路径和容易被忽略的边界条件，都过一遍。文末还会把我自己实际提交时踩过的坑列出来，方便你直接避雷——尤其是那些“本地测试全对，提交OJ就错”的经典翻车现场，我会专门解释原因。

1. 题目解读：别急着写代码，先想明白它到底要你干什么

1.1 这道题究竟在问什么

先看题面的核心信息。题目名称“求迷宫最短通道”，输入一般是一个二维矩阵，若干行若干列，里面有起点、终点、墙壁（不可通行）和空地（可通行）。输出要么是最短路径的长度，要么是完整路径，要么两者都要。7-39这个题号通常意味着这道题来自某套PTA或ACM训练题集，对输出格式有严格约束，比如“每走一步的坐标用→连接”。

这类题目的考察点其实很集中：确认你是否理解“无权图的最短路径为什么只能用BFS”，以及“BFS为什么能找到最短路径”，而不是仅仅背会了某个BFS模板。你要是能把这两个问题回答清楚，代码怎么写几乎就不成问题了。

1.2 最关键的建模步骤：把迷宫变成图

很多同学一看到“迷宫”两个字，脑子里全是“地图寻路”那种概念，但实际处理时，我们需要刻意地把它抽象成一张图。

• 迷宫的每个单元格 = 图的一个节点（node）。
• 相邻可通行单元格之间 = 一条无向边（edge）。
• 起点和终点 = 两个特殊节点。
• 墙所在的位置 = 不存在的节点，或者说根本不在图里。

因为每一步移动的代价都是1，这是一张无权图。对于无权图，求两个节点之间的最短路径，第一直觉不要是Dijkstra，用BFS就够且最优。这里有个容易混淆的点：如果题目改成了“每个格子消耗的体力不同”，那就是有权图，需要换成Dijkstra；但原题明说“最短通道”，且没有代价，那BFS就是标准答案。

注意：BFS能保证第一次到达终点时路径最短，这个结论建立在一个关键前提上——队列中所有节点是按距离从近到远逐层扩展的。后面我会在代码层面验证这句话。

1.3 坐标系的坑：行是r，列是c，别搞反

看题要先看它的坐标定义方式。绝大多数迷宫题输入是先给行数再给列数，比如“5 6”表示5行6列。下标有时候从0开始，有时候从1开始，全看题目怎么说。

• 如果是0-based，那么左上角是(0, 0)。
• 如果是1-based，那么左上角是(1, 1)。

我见过太多同学在这里栽跟头：方向数组写得没问题，但坐标读入时写反了，导致输出路径的格式一直在“行、列”之间反复横跳。我的建议是：先在纸上画一个5×6的格子图，把行索引和列索引标清楚，再写代码。尤其是print路径的时候，一定要看题目要求的是“行在前还是列在前”。

2. BFS核心逻辑：为什么队列能做到“第一次就是最短”

2.1 一句话讲透BFS的层级扩展

BFS的原理，用大白话说就是“一圈一圈地往外找”。从起点开始，先把距离为1的所有节点全部找出来；再从这些节点出发，找距离为2的所有节点；以此类推。因为是按层推进的，所以当某一层里出现了终点，你就能立刻断定：这就是最短的层数，因为比它更短的层你已经全部找完并确认过没有终点了。

这个过程用到队列，先进先出：上一层的节点必须先被扩展完，下一层的节点才可能被拿出来扩展。如果你用栈（也就是DFS），就变成了“一条路走到黑”，找到的第一个终点不见得是最短路径。这也就是说为什么queue和stack的选择基本决定了这个题目的对错。

2.2 为什么需要visited数组而不是每到一格都标记地图

实现BFS时，关于“走过的地方要不要做标记”这个问题，有两种常见做法：直接把迷宫数组里的0改成1，或者另开一个visited布尔数组。两种都能跑通，但我倾向于用独立的visited数组。

原因有两个：

第一，不污染原始地图。调试的时候我想反复打印地图看扩展轨迹，如果原地改了地图，第二遍跑就什么都看不出来了。

第二，有些扩展题目（比如要求输出最短路径长度和具体方案数）需要dis[r][c]记录每个位置的最短距离。这个距离数组本身就能当visited用：只要dis[nr][nc]还是-1，就说明这个格子还没被访问过。用距离数组一石二鸟，既记录步数又充当访问标记。

2.3 方向数组的写法与顺序问题

方向数组通常是这样定义的：

dr = [-1, 1, 0, 0] dc = [0, 0, -1, 1]

分别对应：上、下、左、右。顺序随便，结果都一样。但要注意：四个方向逐一判断时，千万别漏掉边界检查，也就是nr必须在[0, R)区间内，nc必须在[0, C)区间内。任何语言你都得防数组越界。

我自己习惯把方向定义成列表，每个元素是一个二元组：

DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

这样写起来只要一层循环就够了，不用维护两个平行的数组，少一个下标错位的隐患。

3. 代码实现：从0到1写出能AC的完整程序

3.1 基础版本：用队列跑BFS，记录步数

我先把代码写出来。假设输入格式是这样的：

5 5 S . . # . # . # . . . . . . # . # # . . . . . . E

其中S是起点，E是终点，#是墙，.是空地。要求输出从S到E的最短步数，如果到不了输出-1。

from collections import deque def bfs(maze, start, end): R = len(maze) C = len(maze[0]) sr, sc = start er, ec = end dist = [[-1] * C for _ in range(R)] dist[sr][sc] = 0 q = deque([(sr, sc)]) DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)] while q: r, c = q.popleft() if (r, c) == (er, ec): return dist[r][c] for dr, dc in DIRS: nr, nc = r + dr, c + dc if 0 <= nr < R and 0 <= nc < C: if maze[nr][nc] != '#' and dist[nr][nc] == -1: dist[nr][nc] = dist[r][c] + 1 q.append((nr, nc)) return -1

这段代码的核心逻辑其实只有几行：出队一个节点，判断是否终点，不是就扩展四个方向。重点理解dist[nr][nc] == -1这个条件。它同时干了两件事：防止走回头路，保证节点只入队一次。如果你去掉这个判断，队列会无限膨胀，因为节点会在两个方向间反复出入队。

3.2 升级版：同时输出最短路径本身

如果题目要求输出类似(0,0)->(1,0)->(2,0)->...这样的路径，我们就得额外记录每个节点的“前驱节点”，也就是“我是从哪个格子走来的”。这时候队列里存的不只是一个坐标，而是一个包含坐标和前驱信息的对象，或者在搜索过程中用一个parent[r][c]二维数组单独记录。

from collections import deque def bfs_with_path(maze, start, end): R, C = len(maze), len(maze[0]) sr, sc = start er, ec = end parent = [[None] * C for _ in range(R)] parent[sr][sc] = (-1, -1) # 起点没有前驱 q = deque([(sr, sc)]) DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)] while q: r, c = q.popleft() if (r, c) == (er, ec): break for dr, dc in DIRS: nr, nc = r + dr, c + dc if not (0 <= nr < R and 0 <= nc < C): continue if maze[nr][nc] == '#' or parent[nr][nc] is not None: continue parent[nr][nc] = (r, c) q.append((nr, nc)) # 如果终点还是None，说明不可达 if parent[er][ec] is None: return -1, [] # 从终点倒推回起点 path = [] cur = (er, ec) while cur != (-1, -1): path.append(cur) cur = parent[cur[0]][cur[1]] path.reverse() return len(path) - 1, path

这里有一个细节：为什么回溯时用while cur != (-1, -1)而不是“直到起点”？因为我专门给起点设了特殊标记(-1, -1)，所以追溯循环可以很干净地结束。如果你不想用这个特殊值，也可以判断cur != start，但那就要求起点的前驱保持为None，逻辑上也是等价的。

3.3 手动模拟一遍BFS扩展，把过程画在纸上

我强烈建议你至少手动模拟一个小迷宫，比如3×3：

S . . # # . . . E

BFS的执行过程如下：

1. 初始队列：[(0,0)]，dist[0][0] = 0。
2. 出队(0,0)，发现不是终点，扩展右方(0,1)和下方(1,0)。但(1,0)是墙，所以只入队(0,1)，dist[0][1] = 1。
3. 出队(0,1)，扩展其右方(0,2)和下方(1,1)。(1,1)是墙，只入队(0,2)，dist[0][2] = 2。
4. 出队(0,2)，扩展下方(1,2)，入队，dist[1][2] = 3。
5. 出队(1,2)，扩展下方(2,2)，dist[2][2] = 4。
6. 出队(2,2)，是终点，返回4。

从S到E的路径是：(0,0)->(0,1)->(0,2)->(1,2)->(2,2)，确实4步。这个手推过程看起来枯燥，但它能帮你调试。等你敲完代码，发现输出和手推对不上，基本就是方向数组或者边界条件写错了。

4. 踩坑实录：那些让OJ判WA的细节

4.1 多组测试数据的while循环陷阱

很多OJ题不是只跑一组数据，而是不停读，直到文件结束。这时你需要把核心逻辑包在while循环里：

import sys def solve(): lines = sys.stdin.readlines() idx = 0 while idx < len(lines): R, C = map(int, lines[idx].strip().split()) idx += 1 maze = [] for _ in range(R): maze.append(list(lines[idx].strip())) idx += 1 # ... 解析起点终点、跑BFS、输出结果

我第一次做这题时犯的错误是：只读一组数据直接跑，本地样例过了，却因为没处理多组输入而超时或WA。建议你提交前先看一眼题目的输入描述，明确说的是“单组输入”还是“多组输入直到EOF”。

4.2 字符串和二维数组的读写不一致

读迷宫数据时，一行可能是"S..#."这种纯字符串。如果你用list(line.strip())，得到的是字符数组。但如果你后续用maze[r][c] == '.'去判断空地，千万别把坐标行列写反。另外，检查一下行尾有没有\r字符——在Windows环境下读取文件时，\r\n中的\r可能被读进去，导致你的字符判断永远不成立。稳妥的做法是line.strip()。

4.3 起终点本身就是墙，或者起点等于终点

这是极端的边界情况，但题目设计者就爱考这个。

• 如果S和E是同一个格子，最短步数就是0。你的BFS代码应该能自动处理，因为出队起点的判断会让它直接返回0。
• 如果S或E被墙围死，BFS完全走不出去，最后要输出不可达标记。
• 如果起点就被读成了墙，要么数据有问题，要么你的字符处理有bug。

我建议在解析阶段就把起点终点的合法性检查做了，避免图个方便导致后期调试困难。

4.4 坐标是列先行后，还是行先列后

这个问题我再强调一遍，因为它的错误率特别高。有的题目输入一行坐标时，写的是“列 行”，也就是“x y”而不是“row col”。我曾在某套PTA题集里遇到过坐标写成(x=列, y=行)的题目，不仔细看题直接被摆了一道。你在写路径输出时也要跟题目要求对齐，别自己觉得“行优先合理”就改了输出顺序，OJ只认题面。

4.5 队列用popleft还是pop，决定你是BFS还是DFS

在Python里，list.pop()默认弹出末尾元素，用的是栈逻辑；collections.deque.popleft()才是从队首弹出，才符合BFS。别小看这个区别，我曾经在某个版本的代码里图省事，直接拿list当队列用，又把pop()当成了弹队首，结果跑了半天，输出一条蛇形路径，怎么想都觉得不对劲。后来打印每一步的出队顺序才发现自己写成了DFS。

5. 常见问题速查表与调试技巧

5.1 问题与排查方法对照表

5.2 一个笨但有效的调试方法：可视化dist矩阵

BFS跑完以后，dist矩阵就是你最好的调试工具。比如这个迷宫：

S 1 2 3 # # # 4 8 7 6 5

哪怕不画图，光看数字的递增方向你就能判断扩展顺序是否符合预期。如果发现数字跳变混乱，比如一处从1直接跳到5，说明中间有几层没扩展就被你跳过了。这时候回去查方向数组或边界条件就行。

代码里加一段打印矩阵的逻辑：

for row in dist: print(" ".join(f"{x:2d}" if x != -1 else " #" for x in row))

调试完记得删掉，或者用一个开关变量控制，别把调试输出留到提交版本里。有的OJ会有“多余输出”判定，光这个就能让你WA。

5.3 数据规模与复杂度：为什么这门课不推荐DFS

如果迷宫是100×100，BFS的时间复杂度是O(R×C)，也就是最多访问一万个格子，空间复杂度也是O(R×C)。DFS虽然在某些时候能找到解，但在最坏情况下可能会访问整张图的所有路径组合，指数级爆炸。更重要的是，DFS求出来的第一条路径不保证最短。有一些同学反驳说“我可以用DFS记录所有路径再取最短”，确实可行，但递归深度一旦超过系统栈限制，直接爆栈。所以我一般会说：无权图求最短路，优先写BFS，这是刻进DNA里的选择。

6. 优化与扩展：把最短路径问题延伸到实际场景

6.1 双向BFS：让搜索量减半

如果你后续在更大的地图上做路径规划，比如游戏开发里的寻路，可以考虑双向BFS：同时从起点和终点向外扩展，两边轮流各走一步，直到两边的访问区域相交。当图规模很大时，双向BFS能把搜索空间从单向的b^d降到约2 * b^(d/2)，指数级别的收益。

实现思路并不复杂：维护两个队列、两个距离数组，每轮扩展较小的一边。判断相交的标准是：下一个节点在另一边的距离数组里已经被访问过。这个优化在这道OJ题里用不上，但值得了解，因为面试中偶尔会被问到“BFS还能怎么优化”。

6.2 A*搜索：引入启发式，更快找到目标

如果把迷宫里的每个格子当做一个带坐标的节点，A*本质上是在BFS/Dijkstra的框架上加入一个启发函数h(n)，通常用曼哈顿距离估算“当前格子到终点还差多远”，并让优先队列按g(n)+h(n)排序。这样搜索会偏向终点方向，而不是像普通BFS那样向四面八方均匀扩展。

这个观点很重要：A找到的路径仍然是最短的，只要启发函数满足“可采纳性”（也就是不高估剩余距离）。在实际的地图寻路、游戏AI里，A比BFS常用得多。但它的实现复杂度也高一些。如果这道题你已能顺畅写出BFS，作为学有余力的扩展，A*是很好的下一步。

6.3 从单源最短路到多源最短路

有些稍复杂的迷宫题会问：“从区域内任意几个点出发，哪一个点到终点的距离最近？”这种问题本质上就是多源BFS：把所有源点都初始放进队列，distance都设为0，然后一起扩展。第一次遇到终点时，就能知道是哪个源点最快到达。这个方法在图像处理、区域填充、最近邻搜索里都能看到影子。理解了单源BFS之后，多源BFS只是初始化队列时多塞几个点的问题，思维负担很小。

6.4 路径平滑与回溯优化：实操中不可忽略的小事

把最短路径本身输出出来，代码其实不难，但有个小坑：如果你沿路径打印坐标，记得每一对坐标之间是否要加箭头，末尾是否要换行。题目的输出规范通常卡得很细。我的经验是先把路径存成一个列表，最后join输出，这样最不容易出错：

print("->".join(f"({r},{c})" for r, c in path))

实测下来，这样格式控制非常稳，也方便你临时加上起点终点标记。

7. 关于这道题，我最后想说的几点经验

这道迷宫最短通道题，单独看难度不高，但它串联了图论建模、队列数据结构、方向数组、状态标记和路径恢复这几大基础知识点。作为练手题，它的性价比非常突出。我见过很多同学把BFS模板背得滚瓜烂熟，但遇到“输出具体路径”的变体就卡壳，原因就是没理解parent数组的原理。所以我的建议是，学BFS时多花时间在原理上，而不是刷题量。

实际写代码时，我的个人习惯是：先把方向数组和边界检查写完整，再写状态标记，最后才写终点的判断逻辑。因为前三者写错，后面全是错；而终点判断写错，最多是返回值不对，还有机会通过调试去修正。这种自底向上的构建方式，能让我在写大段的搜索逻辑时不至于迷失。

如果你做完这道基础题，接下来可以尝试把代码稍作改造，去解决更贴近实际的地图寻路问题。比如游戏里小怪找玩家，可能就要在BFS基础上加入动态障碍物更新；导航软件里算通勤时间最短的路线，实际上是把迷宫扩展加权图加上实时路况，再用Dijkstra或A*来做。换句话说，今天你在这里写下的这几十行BFS，很可能就是未来很多复杂路径规划系统的源代码雏形。

再提醒一遍：提交OJ之前，把调试用的打印全删掉，仔细对一遍输出格式，确认多组输入的处理方式，再点提交。祝你们一次AC。