说到“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×3S . . # # . . . EBFS的执行过程如下初始队列[(0,0)]dist[0][0] 0。出队(0,0)发现不是终点扩展右方(0,1)和下方(1,0)。但(1,0)是墙所以只入队(0,1)dist[0][1] 1。出队(0,1)扩展其右方(0,2)和下方(1,1)。(1,1)是墙只入队(0,2)dist[0][2] 2。出队(0,2)扩展下方(1,2)入队dist[1][2] 3。出队(1,2)扩展下方(2,2)dist[2][2] 4。出队(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 问题与排查方法对照表现象可能原因排查方法输出路径长度比手算大坐标行列读反打印起点终点的坐标和题目样例对一下输出长度比手算小路径绕近路但实际被墙阻挡打印整个dist矩阵看每一层的值队列无限循环忘记标记visited节点反复入队检查dist[nr][nc] -1条件是否存在数组越界报错边界检查写错或漏写检查0 nr R和0 nc C输出路径反了回溯时没有reverse打印前先path.reverse()或使用deque反向插入同一个测试点时过时不过没处理多组输入看题面输入说明改成while循环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×100BFS的时间复杂度是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。