如果你学过 DFS第一次拿到一本通 P1215「迷宫」这道题十有八九会花二十分钟写一个递归搜索然后盯着评测页面的 TLE 发呆。这道题真正想让你 get 的是在无权图里找最短路径时BFS 凭什么比 DFS 更靠谱以及怎么写才能不超时、不越界、不踩输入输出的坑。题目本身不复杂就是在一个 n×n部分版本是 n×m的迷宫里从起点走到终点只能上下左右移动遇到障碍物不能走求最短步数。听起来和搜索入门题没什么区别但它在「一本通」里的位置很有意思——放在 DFS 章节之后、BFS 章节附近很多人用 DFS 也能跑出答案可一旦数据范围变大或者评测机状态不稳定DFS 的短板就暴露得非常明显。这篇文章我就按自己做这道题的完整思路来拆从读题、选算法、敲代码到排查 TLE/WA/MLE最后聊聊这道题怎么延伸到更多竞赛和面试场景。1. P1215 这道迷宫题很多人的错不在算法在读题1.1 题目描述的版本差异先确认你手上是哪种「迷宫」在信息学奥赛一本通的在线测评系统里出现过多个版本不同学校机房、不同 OJ 的镜像站题面描述可能略有差异。最常见的框架是这样的第一行读入一个整数 n表示迷宫是 n 行 n 列接下来 n 行每行 n 个字符.表示可走空地#表示障碍物最后一行或最后两行给出起点坐标和终点坐标输出从起点到终点的最短步数若不可达则输出某个约定值通常是-1或对应提示。但我也见过输入是0和1的版本0表示可走、1表示不可走还见过起点终点用S和E字符直接标在迷宫里的版本。这些差异不影响算法核心但影响你的读入代码怎么写。最稳的做法是拿到题先看样例再看数据范围最后确认输出格式三步缺一不可。1.2 坐标从 0 还是 1 开始能直接决定你 WA 还是 AC这是 P1215 最容易翻车的地方之一。有的题面说坐标从 1 开始比如(1,1)是左上角有的 OJ 内部存储按 0 开始题面却不写清楚。如果读入的是 1-based 坐标你忘了减一那么起点就会整体偏移一格在迷宫边缘的部分测试点甚至可能直接访问到越界下标。我第一次做这道题就吃过这个亏本地测试样例全过提交后前两个点 WA当时完全不知道问题出在哪。后来把读入的坐标打印出来发现起点和终点的行、列号都比实际大了 1这才意识到题面的坐标系和我的数组下标对不上。建议写一个readPoint()之类的统一封装在读入后就完成坐标转换struct Point { int x, y; }; Point readPoint(int offset -1) { int x, y; cin x y; return {x offset, y offset}; }如果确认题面是 1-based就用默认 offset -1如果是 0-based就传 0。这样至少把坐标系问题控制在一个函数里排查起来方便。1.3 边界条件起点等于终点、起点被障碍包围、终点不可达再简单的搜索题也有三个边界 case 值得提前想清楚起点就是终点BFS 的循环还没开始就应该返回 0有些写法会把起点入队后立刻判断有些则会在第一次 pop 时命中两种都能过但你要确保自己没漏掉这种情况起点周围全是障碍起点可以入队但四个方向都扩展不出去队列很快清空正确输出应是不可达标记终点本身是障碍严格来说这种情况题面通常不会给因为起点和终点一般保证是空地但防御性写法里最好在 BFS 前检查一下map[ex][ey]是否合法避免读到#却走出一个错误答案。这些边界 case 不需要你写多复杂的特判只需要在写 BFS 的时候保持「先判越界再判障碍再判访问标记」的顺序就能天然规避大部分问题。2. 为什么标准解是 BFS 而不是 DFS一场关于搜索顺序的较量2.1 DFS 能出答案但代价你可能承受不起不少初学者看到迷宫题第一反应是递归 DFS从起点出发向四个方向试探走到终点就更新一次步数最后输出最小值。对于 n5、n10 的小迷宫这种做法完全可行代码还特别直观void dfs(int x, int y, int step) { if (x ex y ey) { ans min(ans, step); return; } // 四个方向试探 }问题在于DFS 在找「最短路径」时本质上是在暴力枚举所有从起点到终点的路径。如果迷宫是一个 100×100 甚至更大的网格路径数量会指数级暴涨。你以为自己只走了一遍迷宫实际上 DFS 可能把同一条走廊来回走了几十遍因为递归回溯时会反复经过同一个格子。我实测过一个 50×50 的随机迷宫DFS 求解最短路在老家电脑上大概跑了三秒多同样是这个迷宫BFS 不到一毫秒就出来了。在信息学奥赛的评测环境下这种差距就是 TLE 和 AC 的差距。2.2 BFS 的「层」天然对应最短步数BFS 为什么能保证第一次搜到终点时步数最短关键在于队列的先进先出特性所有距离为 k 的节点一定会在距离为 k1 的节点之前出队。把起点看成第 0 层起点一步能到达的所有格子看成第 1 层两步能到达的看成第 2 层……BFS 逐层向外扩展就像水面丢下一颗石子波纹一圈一圈往外扩散。第一圈到达终点的路径必然是最短路径因为如果存在更短的路径它应该属于更早的层早就该被扩展到了。这一点与 Dijkstra 算法有异曲同工之处当所有边的权值都为 1 时BFS 就是 Dijkstra 的特例。2.3 为什么不能用 DFS 加剪枝代替 BFS有人会问DFS 加一个「当前步数 当前最优解就剪枝」是不是就能过了在小数据量下确实能过但剪枝的效率和迷宫形态强相关。如果迷宫是一条笔直通道DFS 第一次就走出了最优解剪枝效果很好但如果是「回字形」迷宫DFS 会先把所有错误方向的路径探到底剪枝晚且效率低。更麻烦的是DFS 的递归深度可能达到迷宫的格子总数。n100 时递归深度上万是常有的事而系统栈默认大小通常只有 8MB 左右极端情况下会直接爆栈RE/MLE。BFS 用队列存储节点内存可控栈深度问题完全不存在。所以这类最短路问题BFS 是更符合题意的标准解。3. 核心代码拆解pair 队列、方向数组、距离标记的三板斧3.1 一版可以直接抄的 BFS 模板先给出一份可以在 C17 环境下直接编译运行的代码。这个版本不用结构体用pairint,int存坐标配合dist数组同时记录距离和访问状态。#include bits/stdc.h using namespace std; const int MAXN 105; int n; char mp[MAXN][MAXN]; int dist[MAXN][MAXN]; bool vis[MAXN][MAXN]; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; int bfs(int sx, int sy, int ex, int ey) { if (sx ex sy ey) return 0; queuepairint, int q; q.push({sx, sy}); vis[sx][sy] true; dist[sx][sy] 0; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 越界检查 if (nx 0 || nx n || ny 0 || ny n) continue; // 障碍检查 if (mp[nx][ny] #) continue; // 访问标记检查 if (vis[nx][ny]) continue; vis[nx][ny] true; dist[nx][ny] dist[x][y] 1; if (nx ex ny ey) { return dist[nx][ny]; } q.push({nx, ny}); } } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; for (int i 0; i n; i) { cin mp[i]; } int sx, sy, ex, ey; cin sx sy ex ey; // 如果题面坐标是 1-based这里记得 --sx 等转换 sx--; sy--; ex--; ey--; memset(vis, 0, sizeof(vis)); memset(dist, 0, sizeof(dist)); cout bfs(sx, sy, ex, ey) endl; return 0; }这份代码有几个值得注意的地方用pairint,int而不是自定义结构体代码更简洁和 STL 容器配合也更自然dist和vis共用也可以因为dist初始化为-1就能兼作访问标记但这里分开写是为了初学者理解清晰ios::sync_with_stdio(false)和cin.tie(nullptr)在数据量大时能显著提升输入输出效率竞赛习惯一定要养成。3.2 为什么要在入队时标记 vis而不是在出队时标记这是我在讲 BFS 时最爱强调的一个点也是很多新手从 DFS 转 BFS 时最容易犯的错。如果你把vis[nx][ny] true这一行挪到q.push({nx, ny})之后或者在循环里只在q.pop()时才标记那么同一个格子可能被多个相邻格子重复加入队列。举个例子格子 A 和格子 B 都能一步走到格子 C如果 A 先扩展出 C但 C 出队前没有标记B 扩展时又会把 C 加入一次。在小范围迷宫上这种重复最多让队列膨胀几倍在大范围迷宫里重复入队会导致队列呈指数级膨胀直接 TLE 甚至 MLE。用一句话记住入队即认领出队不重复。只要一个节点入了队就立刻标记为已访问这是 BFS 的黄金准则。3.3 方向数组的顺序会影响答案吗dx/dy的顺序无论是上、下、左、右还是任意排列都不影响最终的最短步数答案因为四个方向的移动代价完全相同。它只影响在「多个同样短路径」中你会先枚举哪一条。不过在实际调试时建议固定一个习惯顺序比如我习惯上、下、左、右对应{-1,1,0,0}和{0,0,-1,1}。这样当你想复现一个 bug 时可以稳定地知道搜索的方向顺序不至于每次运行结果在路径选择上飘忽不定。3.4 时间复杂度每个格子最多被扩展一次BFS 的时间复杂度为 O(n²)空间复杂度也是 O(n²)n 是迷宫的边长。每个格子在入队后立刻被标记因此最多出队一次每个出队节点检查四个方向总操作次数大约是4 × n²的常数倍。这个复杂度意味着 n1000 的迷宫也能在一秒内轻松跑完。相比之下DFS 的最坏复杂度是指数级的两者在数据范围扩大时差距会越来越夸张。这也是为什么竞赛题里只要题目明确「求最短步数」BFS 几乎永远是正解。4. 实测踩坑TLE、WA、MLE 的三种排查链路还原4.1 一次 TLE 的完整排查入队时机与队列膨胀有一年带集训队一个学生交上来的 P1215 代码长这样简化后while (!q.empty()) { auto [x, y] q.front(); q.pop(); vis[x][y] true; // 出队时才标记 for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 || nx n || ny 0 || ny n) continue; if (mp[nx][ny] #) continue; if (vis[nx][ny]) continue; dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } }逻辑看起来没什么问题但评测结果稳 TLE。我们把队列长度打印出来发现 n100 的纯空地里队列峰值达到了一万多个节点而理论上应该只有一万个左右。问题就出在出队才标记这段延时上一个节点入队后如果还未出队就不算 visited那它的所有邻居都能再次入队造成大量重复。排查链路在q.push前打印当前坐标和入队坐标观察是否出现同一个坐标被多次入队统计dist数组里被赋值的格子数如果大于总格子数说明重复入队对照正确代码确认标记位置应该放在入队时而不是出队时。这个问题也说明了为什么竞赛代码不用「先入队、出队标记配合 if 判断」这种冗余写法——一步错步步错不如直接遵守最简单的标记准则。4.2 一次 WA 的完整排查坐标映射与多组数据残留另一个学生的情况更隐蔽本地样例全过提交后一半 WA一半 AC。排查过程先看 WA 的点基本都是边界坐标比如(1,1)或(n,n)本地测试时用的输入数据全是小坐标没触发越界打印读入后的sx、sy发现起点是 1-based 的(1,1)但数组里被当成 0-based 的(1,1)处理实际上访问的是(1,1)而非(0,0)等于整体偏移了一格。还有一个类似问题是多组测试数据的残留。如果题目有多个 case而你的vis和dist数组没有在每组数据开始前memset重置上一次的访问标记会污染下一次搜索导致明明能走通的路被判为已访问。这个坑在单组数据的 P1215 里不容易遇到但在部分改版题里会出现防御性写法就是每组开始前清空数组。4.3 一次 MLE 的完整排查DFS 爆栈与递归深度还有一个学生直接用 DFS 递归做这题本地 n30 的小数据能过评测数据一上来就 RE/MLE。原因是递归深度和系统栈的分配问题。DFS 在一个完全空白的迷宫里最大递归深度可能达到 n² 2500每一次递归调用都要在系统栈上分配若干字节理论上总占用不会太大。但有些 OJ 开启栈保护或递归次数受限后深度较大的递归很容易被判为运行时错误。换成 BFS 之后内存主要消耗在队列的节点存储上最大也只是 O(n²) 个节点完全在可控范围内。这也提醒我们在信息学竞赛里就算某些搜索题 DFS 能过也要想清楚数据范围有多大、递归深度会不会成为隐患。BFS 是更保险、更规范的解法。4.4 常见错误对照表问题现象常见根因排查方向运行超时 TLE出队时才标记 vis导致大量重复入队检查标记位置改成入队即标记答案错误 WA坐标系 1-based/0-based 转换漏减一打印起点终点坐标核对数组下标答案错误 WA多组数据未清空 vis/dist 数组每组数据前 memset内存溢出 MLEDFS 递归深度过大栈溢出改为 BFS或调大编译栈空间运行时错误 RE数组越界尤其是迷宫边界判断缺失在访问数组前加越界判断输出格式不对题目要求输出特定字符串你输出了数字重读题面输出要求5. 从 P1215 延伸开最短路径的进阶变式与自适应迷宫5.1 第一跳不只是步数还要打印路径很多同学做完基础版会问如果题目要求输出完整路径而不是步数怎么办思路很简单——加一个pre数组记录每个节点是由哪个节点扩展而来。由于 BFS 天然按层扩展从终点沿着pre回溯到起点得到的路径就是最短路径之一。struct Node { int x, y; Node *pre; // 指向父节点 };或者更节省内存的方式用两个二维数组记录每个节点的父坐标。到终点后从终点开始向上回溯把坐标压进栈再输出就能得到正序路径。这个变式在很多迷宫类题目中出现频率不低同时也是「输出路径」类 BFS 题目的通用解法。5.2 第二跳分层图、传送门与多源 BFS当迷宫加入传送门、钥匙、门锁等元素后简单的二维 BFS 就不够用了。此时通常需要引入「状态」的概念——不只是坐标还要加上当前持有的钥匙状态、当前使用过的传送门等然后用三维甚至更高维的 visited 数组记录状态进行 BFS 扩展。举个例子迷宫里有几把钥匙和对应的门那么状态就是(x, y, mask)其中mask是一个整数每一位表示是否持有某把钥匙。搜索时从每个坐标出发可以多考虑「捡钥匙」和「开对应门」两种操作。这就是所谓「状态压缩 BFS」的原型。多源 BFS 更容易理解如果起点有多个你希望找到从任意起点出发到终点的最短距离可以把所有起点一次性都放进队列然后正常跑 BFS。由于队列的层级特性第一次访问到终点时一定是从某个最近起点扩展过来的结果。5.3 第三跳自适应迷宫算法是什么和这道题有什么关系最近不少人讨论「自适应迷宫算法」这个词在竞赛圈更多是一种概念延伸指的是在迷宫环境动态变化、或者不知道完整地图的情况下如何边探索边更新路径。经典 BFS 需要完整的地图信息而自适应场景里机器人只能看到自己周围一小块范围随时可能遇到新障碍需要重新规划路径。这类问题在真实世界的导航、扫地机器人路径规划里更常见。竞赛中对应的是「动态障碍物 BFS」「在线重规划」等题目。经典做法是走几步就重新跑一次 BFS/A*把最新探测到的障碍信息加入地图或者用 D* Lite 这类增量式寻路算法避免每次从零搜索。回到 P1215它虽然没有这些高级设定但打个比方如果你理解了 BFS 为什么能高效地在已知地图里找最短路径那么自适应迷宫无非是在地图更新后快速重算或者结合启发式函数减少搜索范围。基础不牢后面这些花活根本没法玩。我在实际练题过程中的一个体会是迷宫题是个「百变题型」从最朴素的 BFS 到分层图、状压、多源搜索再到 A*、D*每一步进阶都建立在最基础的那一次出队入队之上。P1215 这个题号虽小但它串联起的知识链条几乎覆盖了图论最短路搜索的半壁江山。强烈建议你做完这道题后随手把打印路径的变式也写一遍再尝试改造成状态压缩 BFS 的框架遇到瓶颈了再回来看看这份基础代码——你会发现所谓难题都是这些基础动作的组合。
