初看“pta-7-52 求解迷宫从入口到出口的所有最短路径(DFS)”这个题很多人会觉得不就是个递归搜索嘛结果动手一写就卡住了。其实这道题把DFS、回溯、剪枝、最短路预计算四个知识点全串在一起而且“所有最短路径”这个要求直接让难度上了一个台阶。适合正在学DFS回溯的初学者、准备机试或复试的选手以及所有想搞明白“搜索到底怎么剪枝才优雅”的人。我自己当年在这道题上也熬了不少时间这篇就把完整的求解思路、代码和踩坑经验全部分享出来。1. 题目到底在问什么先别急着写代码1.1 输入输出约定这类迷宫题最常见的约定是先输入迷宫的规模m行n列然后给一个m行n列的矩阵0表示空地可以走1表示墙壁不能走。默认左上角是入口右下角是出口也就是从(0,0)出发走到(m-1,n-1)。题目要求你把从入口到出口的所有最短路径全部枚举出来而不是只输出一条。输出部分不同版本要求略有差异有的要求输出每条路径经过的坐标序列有的还要求先输出最短路径长度或路径条数。我看到过有些题目对坐标格式和分隔符卡得很死多一个逗号、少一个箭头都会判WA。所以拿到题先仔细看样例格式这个细节比算法本身更容易让你丢分。1.2 题目里容易忽略的三个细节第一个细节是“入口或出口本身可能是墙”。有些测试用例上来就把入口堵死这种情况不管你怎么搜都是无解写代码时最好单独判断一下或者直接在BFS结果里判断起点dist是否为-1两个做法都可以。第二个细节是“最短路径可能不止一条”。这是和普通迷宫题最大的区别。很多人一搜到终点就return结果只输出了一条路径白丢一半的分。你要做的是把当前这条路径记录下来然后继续回溯搜索把所有同样长度的路径全部枚举完。第三个细节是“方向遍历的优先级”。PTA这类题经常对方向遍历顺序有隐式要求比如“优先向下、再向右、再向上、再向左”如果你的方向数组是随便写的即使路径都对输出顺序不对照样WA。方向数组的顺序从一开始就要设计好后面我会详细说。2. 方案选型为什么我最终选择了“反向BFS DFS剪枝”2.1 纯BFS的问题在哪里如果题目只问最短路径长度BFS是天然的解它按层扩展第一次到达终点的层数就是最短距离。但题目要的是“所有最短路径的完整坐标序列”这时候BFS就难受了。BFS在扩散过程中每个节点通常只记录一个前驱或一个距离要还原出完整的路径集合得额外存每个点在最短路径意义下的所有前驱然后从终点倒着回溯拼路径代码量反而比DFS大逻辑也更绕。当然有BFS多前驱的做法但处理重复节点、去重、回溯拼接这些细节对新手不太友好。我觉得这道题的教学重点其实在DFS的回溯枚举所以更适合用DFS来做路径收集。2.2 纯DFS的问题在哪里DFS天然适合枚举所有解因为回溯就是干这个的。但这里有个致命问题如果不加约束DFS会枚举出指数级别的路径数量包括大量绕远路、回头路。就算题目迷宫规模只有10x10路径数量也可能大到跑不完直接TLE。那我们就要想能不能让DFS在枚举的过程中只走到“有可能出现在某条最短路径上”的格子答案是肯定的这就需要先用一次BFS把“距离场”算出来。2.3 组合拳思路先算距离再沿“下坡路”枚举我的做法分两步。第一步从终点出发做一次反向BFS得到每个格子到终点的最短步数记为dist[x][y]。dist的值相当于一张海拔图终点高度是0越靠近终点数值越小。第二步从起点出发DFS每次只走向dist值比当前格子恰好小1的邻居也就是“每走一步都离终点更近一格”。这个思路有个直观类比想象你在山上往下走目的地是海拔0的山脚。你每一步都只下降到海拔低1米的位置那你走出来的每一条路长度一定正好等于起点到终点的最短距离。不可能绕路因为绕路意味着某个时刻海拔没有下降而被你的规则直接禁止了。这样一来DFS枚举的每一条路径天然就是最短路径完全不需要在搜索过程中反复比较路径长度。我还尝试过另一种方案先用DFS暴力找一遍最短长度再第二遍DFS枚举所有等于该长度的路径。这种做法在某些数据范围下也能过但毕竟是两次搜索剪枝也不够彻底搜索量偏大。相比之下“反向BFS求距离场 DFS沿递减网格递归”才是更干净、可控性更强的方案强烈推荐。3. 第一板斧反向BFS给迷宫铺一张“距离场”3.1 为什么从终点出发而不是起点出发正着BFS也能算出距离但算出来的是“起点到每个格子的最短步数”对DFS剪枝帮助不大。我们DFS时最需要知道的是“当前格子离终点还有多远”这样才能判断下一步能不能走。所以从终点出发做BFS把终点当源点一层层向外扩散每个格子记录的就是它到终点的最短步数。起点处的dist值恰好就是整条最短路径的长度一石二鸟。3.2 BFS代码实现要点void bfs() { queuepairint, int q; memset(dist, -1, sizeof(dist)); dist[ex][ey] 0; // 终点到终点距离为0 q.push({ex, ey}); while (!q.empty()) { int x q.front().first; int y q.front().second; q.pop(); for (int k 0; k 4; k) { int nx x dir[k][0]; int ny y dir[k][1]; if (nx 0 || nx n || ny 0 || ny m) continue; if (maze[nx][ny] 1) continue; // 墙 if (dist[nx][ny] ! -1) continue; // 已访问过 dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } }这里有一个非常实用的技巧dist数组初始化成-1它同时承担了“未访问标记”和“不可达标记”两个职责。BFS扩展时只要dist[nx][ny]不是-1就说明这个格子已经被访问过直接跳过。等BFS结束如果dist[sx][sy]仍然是-1说明起点根本到不了终点不用再DFS了。3.3 dist数组长什么样以最简单的3x3迷宫为例假设地图是0 0 0 / 0 1 0 / 0 0 0也就是四个方向都能走正中间是墙。从终点(2,2)反向BFS后dist矩阵会是| (0,0) 4 | (0,1) 3 | (0,2) 2 | | (1,0) 3 | 墙 | (1,2) 1 | | (2,0) 2 | (2,1) 1 | (2,2) 0 |看到这个矩阵你就能马上数出起点(0,0)到终点要4步而且能看出哪些方向是“下山方向”起点左边和上边越界右边(0,1)的dist是3下面(1,0)的dist也是3所以两条路都是合法的下降方向。4. 第二板斧DFS回溯只走“下坡路”4.1 核心剪枝条件dist[nx][ny] dist[x][y] - 1这一段是整个算法的灵魂。DFS每走到一个格子(x,y)它的dist值就代表“从这里到终点还要走几步”。如果下一步走到邻居(nx,ny)而dist[nx][ny]等于dist[x][y]说明邻居离终点的距离和当前一样近走这一步等于原地打转不可能出现在最短路径上。只有dist[nx][ny]等于dist[x][y] - 1才说明这一步实实在在地往终点方向逼近了一步。整个过程唯一的判断条件就是这一句if (dist[nx][ny] dist[x][y] - 1) { ... }有些同学会写反成dist[x][y] - dist[nx][ny] 1逻辑上等价但容易在边界情况上糊涂。保持一致写dist[nx][ny] dist[x][y] - 1最好记也最直观。4.2 为什么理论上可以省略vis但我建议加上这是个很有意思的讨论点。沿着dist严格递减的路径走理论上不可能走回头路如果从A走到B满足dist[B] dist[A] - 1那么从B再走回A就必须满足dist[A] dist[B] - 1也就是dist[A] dist[A] - 2矛盾。所以最短路上的路径天然无环vis标记在数学上可以省略。但我实际写代码时仍然会加上vis。原因有两个。第一加了vis后回溯模板更标准路径去重的逻辑更直白不用每一步都去论证“为什么不会绕回来”对初学者更友好。第二很多变体题会删掉dist剪枝条件来让你求“所有路径”这时候vis就是保命符。养成写的习惯换题不慌。4.3 DFS核心代码与回溯三件套void dfs(int x, int y) { if (x ex y ey) { allPaths.push_back(path); // 到达终点记录完整路径 return; } for (int k 0; k 4; k) { int nx x dir[k][0]; int ny y dir[k][1]; if (nx 0 || nx n || ny 0 || ny m) continue; if (maze[nx][ny] 1) continue; if (vis[nx][ny]) continue; if (dist[nx][ny] ! dist[x][y] - 1) continue; // 核心剪枝 vis[nx][ny] true; path.push_back({nx, ny}); dfs(nx, ny); path.pop_back(); vis[nx][ny] false; } }回溯的标准动作是“标记、入路径、递归、还原”。每当递归调用结束回到当前层必须把vis重新设为false把path最后一个元素弹出去这样才能让同一层的其他方向继续尝试。经常有人漏掉vis还原结果路径越搜越少或者出现莫名其妙的重复和遗漏。调这种bug比写代码痛苦得多所以建议从一开始就把这三行当成铁律写全。4.4 方向数组的顺序直接决定输出顺序方向数组的写法会直接影响DFS枚举路径的先后顺序。如果用常见的“下、右、上、左”int dir[4][2] {{1,0}, {0,1}, {-1,0}, {0,-1}};那么DFS会优先走下再走右再走上再走左。这样一来枚举出的第一条路径就是“最优先向下”的那条字典序结果。如果题目要求按“上、下、左、右”或者别的顺序输出你只需要调整dir数组的排列顺序核心逻辑一行都不用动。这里提醒一下dir数组的每个方向要保证四个方向都覆盖到有人图省事只写两个方向结果只搜出单调路径自然不正确。长个记性迷宫四连通就是四个方向八连通才写八个方向。5. 完整AC代码与复杂度分析5.1 一份可直接提交的完整代码把BFS和DFS组合起来整个程序大概长这样#include bits/stdc.h using namespace std; const int MAXN 105; int n, m; int maze[MAXN][MAXN]; int dist[MAXN][MAXN]; bool vis[MAXN][MAXN]; int dir[4][2] {{1,0}, {0,1}, {-1,0}, {0,-1}}; // 下、右、上、左 int sx, sy, ex, ey; vectorvectorpairint,int allPaths; vectorpairint,int path; void bfs() { queuepairint,int q; memset(dist, -1, sizeof(dist)); dist[ex][ey] 0; q.push({ex, ey}); while (!q.empty()) { int x q.front().first; int y q.front().second; q.pop(); for (int k 0; k 4; k) { int nx x dir[k][0]; int ny y dir[k][1]; if (nx 0 || nx n || ny 0 || ny m) continue; if (maze[nx][ny] 1) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } } void dfs(int x, int y) { if (x ex y ey) { allPaths.push_back(path); return; } for (int k 0; k 4; k) { int nx x dir[k][0]; int ny y dir[k][1]; if (nx 0 || nx n || ny 0 || ny m) continue; if (maze[nx][ny] 1) continue; if (vis[nx][ny]) continue; if (dist[nx][ny] ! dist[x][y] - 1) continue; vis[nx][ny] true; path.push_back({nx, ny}); dfs(nx, ny); path.pop_back(); vis[nx][ny] false; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 0; i n; i) for (int j 0; j m; j) cin maze[i][j]; // 默认入口(0,0)出口(n-1,m-1)按题目要求可灵活调整 sx 0; sy 0; ex n - 1; ey m - 1; if (maze[sx][sy] 1 || maze[ex][ey] 1) { // 入口或出口被堵死无解 cout no path endl; return 0; } bfs(); if (dist[sx][sy] -1) { cout no path endl; return 0; } vis[sx][sy] true; path.push_back({sx, sy}); dfs(sx, sy); // 按题目要求输出下面是一种常见格式 cout dist[sx][sy] endl; for (auto p : allPaths) { for (int i 0; i (int)p.size(); i) { if (i) cout -; cout ( p[i].first , p[i].second ); } cout endl; } return 0; }这段代码在结构上非常简单清楚先BFS算距离场判断无解再DFS枚举全部最短路径。放在PTA的评测环境里只要方向顺序和输出格式跟题目要求对齐AC是没问题的。5.2 关键变量一览变量作用备注maze原始迷宫0可走1墙dist每个格子到终点的最短步数-1表示不可达visDFS访问标记防止重复访问path当前正在枚举的路径vector动态维护allPaths所有最短路径的结果集每条路径是一个坐标序列dir方向数组顺序影响输出顺序我建议写题时把变量命名规范成上面这样不要为了省事全用a、b、c。调试的时候变量名越表意越能快速定位问题。5.3 复杂度与数据范围BFS阶段每个格子最多入队一次时间是O(nm)。DFS阶段由于剪枝条件保证每一步都严格向终点靠近所以枚举的路径数量正好等于“最短路径条数”每条路径长度不超过nm总复杂度近似O(L * pathCount)其中L是最短路径长度。在PTA这种题里迷宫规模通常不大这个复杂度远优于纯DFS的指数爆炸。不过要留个心眼如果迷宫是一个完全开阔的空地比如30x30全是0那么最短路径条数会非常庞大DFS枚举所有路径本身就可能超时。遇到这种极端数据通常题目会限制输出条数或者数据范围给得很小。真碰到不限制的情况那就要思考是不是题目考察的其实是动态规划求方案数了。6. 实战踩坑实录与调试技巧6.1 常见错误速查表症状可能原因解决方法输出路径顺序和答案不一致方向数组优先级不对按题目要求调整dir顺序一条最短路径都搜不到起点dist为-1或者起点/终点是墙先检查BFS是否成功再检查墙标记搜出来的路径明显绕远路剪枝条件写错比如等号方向反了确认只有dist[nx][ny] dist[x][y] - 1才走程序卡死或栈溢出没有正确回溯vis没还原检查回溯三件套是否完整输出格式WA箭头、逗号、空格与样例不符逐字符核对题目样例格式起点能走但结果为空起点没有加入path或没有设置vis确保main里先入path再调用dfs这张表是我自己和身边同学经常踩的坑基本上覆盖了八成左右的错误来源。6.2 调试技巧先看距离场再验单条路径我在调试这类搜索题时有一个固定流程首先单独跑BFS把dist矩阵打印出来肉眼检查“终点旁边是不是一圈1再外圈是不是一圈2”这个层级结构只要是对的最短路长度就稳了。然后再在DFS里加一个“抵达终点时打印当前路径”的临时输出看看第一条路径长度是否等于dist[sx][sy]。如果等于说明剪枝逻辑基本正确再放开allPaths收集所有路径。这种分步调试法比一上来就跑完整测试用例高效很多。直接看最终输出万一错了你都不知道错在BFS还是DFS分步定位能省下一半的debug时间。6.3 亲手跑一个3x3例子验证结果还是用前面那个3x3迷宫地图0 0 0 0 1 0 0 0 0反向BFS得到的dist矩阵是| 4 | 3 | 2 | | 3 | 墙 | 1 | | 2 | 1 | 0 |从(0,0)出发dist4能走的邻居只有右边(0,1)和下面(1,0)两者dist都等于3。如果方向数组是“下、右、上、左”那么DFS会先试着走(1,0)。继续推导路径一下右下。过程是(0,0)-(1,0)(1,0)的dist3只能走到(2,0)dist2再从(2,0)走到(2,1)dist1最后走(2,2)dist0到达终点。路径二右右下。过程是(0,0)-(0,1)(0,1)的dist3只能走到(0,2)dist2再从(0,2)走到(1,2)dist1最后走(2,2)结束。两条路径长度都是4全部都能被枚举出来。用这个例子对照代码走一遍你会发现整个算法不需要做任何“当前步数是否大于最短长度”的判断因为每一步都自动踩着最短距离的节拍。6.4 扩展如何只求字典序最小的那条最短路径有些题目不是要所有最短路径而是只想要其中字典序最小的一条。这时你不需要改动算法核心只需要把方向数组按字典序优先级排列比如“下、右、上、左”就是一个常见的排序。DFS按这个顺序搜索第一条到达终点并记录的路径天然就是字典序最小的最短路径。找到后直接return不再继续搜索即可。如果你有兴趣进一步训练可以考虑把dist数组改成从起点正向BFS生成然后想想DFS剪枝条件会变成什么。答案是在DFS中维护一个step变量每次走step 1并且只允许走向dist[nx][ny] step 1的格子同时保证step不能超过dist[ex][ey]。这个改法练一遍你对正向和反向搜索的理解会彻底拉开差距。我个人的体会是这道题真正训练的不是“会写DFS”而是“会先算清楚再搜索”。先花一次BFS的代价把距离场铺好DFS枚举量就从指数级被压缩到“只搜有效路径”这种预处理剪枝的套路在后面的很多题里反复出现。迷宫虽小道理不小值得反复咀嚼。