牛客的每日一题我已经连着刷了两百多天要说出现频率最高的题型“走迷宫”绝对排前三。别小看这道看起来只是一个二维数组的BFS模板题它几乎是所有图论搜索题的敲门砖面试官问在迷宫里找最短路径本质上是考你懂不懂BFS为什么能保证最短、边界怎么处理、状态怎么去重。这篇文章就把这道题从题面拆到代码从普通版本聊到进阶变体最后把我踩过的坑全部列出来。适合刚准备找实习、刷题量在100题上下的同学也适合想系统整理搜索模板的进阶选手。1. 题目拆解与解题思路1.1 题面到底在问什么牛客上的“走迷宫”每次题目描述可能有细节差异但核心框架非常统一有一个 n 行 m 列的网格地图每个格子上有四种字符之一.表示空地可以走#表示墙壁不能走S是起点E是终点。角色每次只能向上下左右四个方向移动一格不能走出地图边界也不能走进墙壁。要求输出从 S 到 E 的最短移动步数如果根本走不到输出 -1。输入格式通常是第一行两个整数 n 和 m接下来 n 行每行一个长度为 m 的字符串。比如这个典型样例5 5 S.... ###.. ..#.. E.... .....从 (0,0) 到 (3,0)沿着左边界一路向下就能到最短步数是 3。这类题表面问的是“能不能走通”实际上问的是“最短走几步”这就决定了算法选型不能用朴素 DFS必须用 BFS。我用一个生活类比帮助理解你站在一个陌生商场里找出口最靠谱的办法不是随便选一条路走到黑而是“这一层所有能一步到达的地方全部看一遍再看两步能到达的地方三步能到达的地方”。谁最先出现在你的视野里谁就是离你最近的出口。这个逐层扩张的过程就是 BFS。1.2 为什么选BFS而不是DFS很多新手看到“找路径”第一反应就是 DFS递归一条路走到底撞墙了再回溯。这道题如果只问“能否到达”DFS 确实可行。但一旦问题变成“最短步数”DFS 就有个大问题你必须把从起点到终点的所有路径全部走完才能知道哪一条最短。最坏情况下路径数量是指数级的在 100x100 的地图里直接超时到怀疑人生。BFS 能保证最短步数靠的是一个很朴素的原理在无权图每条边代价都为1中BFS 是按照“距离起点越来越远”的层次顺序遍历节点的。第一次通过某个格子时走的步数一定是从起点到它的最短步数。因为如果存在更短的路那条路的更短层会先被队列弹出来扩展也就先到达这个格子了。所以这道题的时间复杂度是 O(n×m)每个格子最多入队一次、出队一次空间复杂度也是 O(n×m)主要花在距离数组和队列上。对于最多几百乘几百的地图来说这个复杂度非常舒服。2. 从零搭建BFS模板核心细节拆解2.1 数据结构选型队列、距离数组、方向数组BFS 模板需要三样东西一个队列、一个记录距离的数组、一个方向数组。这三样各有讲究。队列用普通队列就够了C 里用queuepairint,intPython 里用collections.dequeJava 里可以用LinkedList实现Queueint[]。这里有一个新手常犯的错误如果自己用数组模拟队列一定要开够空间二维坐标入队最坏情况是 n×m 个千万别开小了导致数组越界。距离数组我习惯初始化成 -1而不是 0。-1 有双重含义既表示这个格子还没被访问过也表示从起点到它的步数未知。起点初始化为 0扩展时dist[nx][ny] dist[x][y] 1。这样判断是否访问过只需要if (dist[nx][ny] ! -1) continue;一步到位。如果用 boolean 访问数组还得额外用一个步数数组写起来绕。方向数组是四个方向的增量我通常这样写dx {-1, 1, 0, 0} dy {0, 0, -1, 1}分别对应上、下、左、右。四个方向的顺序无所谓不影响最短步数结果只要保证四个方向都遍历到就行。2.2 入队出队时机与访问标记避免重复访问BFS 的循环结构非常固定从队列里取出一个节点检查它是不是终点然后向四个方向扩展。如果能走的格子没有被访问过就更新距离并入队。这里最关键的一点是标记访问的时机必须是在入队的那一刻而不是出队的那一刻。我见过很多人在出队时才标记 visited这样会导致同一个格子被多个邻居重复加入队列。举个例子格子 A 和格子 B 都能走到 C如果 C 在入队时没标记A 先把 C 入队了B 扩展时发现 C 还没被标记又把 C 入队了一次。队列里出现大量重复节点最坏情况下每个格子可能入队多次复杂度被拉爆甚至产生错误结果。正确写法是一旦确定(nx, ny)可以走且没访问过立刻更新距离、入队、标记。三步缺一不可。另一个容易被忽略的细节是边界判断。每次扩展新节点时先判断是否越界if (nx 0 || nx n || ny 0 || ny m) continue;再判断是否撞墙if (grid[nx][ny] #) continue;最后才判断是否访问过。这三个条件的顺序其实可以调换但写成“先边界、再墙壁、再访问标记”的固定顺序能帮你减少思维负担。2.3 步数记录的两种写法dist数组 vs 节点内携带步数步数记录有两种主流写法我分别说一下适用场景。第一种就是我上面介绍的 dist 二维数组。它的优势是直观打印出来就是一个完整的步数地图调试时非常方便。缺点是额外占 O(n×m) 的空间不过对牛客这类题目的数据规模来说完全不是问题。第二种是队列节点里直接带步数。C 里用queuepairpairint,int,intPython 里队列存(x, y, step)。这种写法省掉了 dist 数组但是有个问题你无法在入队时判断这个格子是否已经用更短步数访问过必须额外开一个 bool visited 数组。算下来空间并没有省代码反而更乱。所以我的建议非常明确模板就写 dist 数组版没有特殊情况不要换。一个模板写到肌肉记忆里考试和面试时才能不假思索地默写出来。3. 多语言实现与提交实战3.1 C实现顺带说明I/O技巧C 是我刷牛客用得最多的语言优点是速度快、STL 好用。下面是一份可以直接提交的完整代码#include bits/stdc.h using namespace std; const int MAXN 105; int n, m; char g[MAXN][MAXN]; int dist[MAXN][MAXN]; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; int main() { cin n m; int sx 0, sy 0, ex 0, ey 0; for (int i 0; i n; i) { cin g[i]; for (int j 0; j m; j) { if (g[i][j] S) { sx i; sy j; } else if (g[i][j] E) { ex i; ey j; } } } memset(dist, -1, sizeof(dist)); queuepairint, int q; q.push(make_pair(sx, sy)); dist[sx][sy] 0; while (!q.empty()) { pairint, int cur q.front(); q.pop(); int x cur.first, y cur.second; if (x ex y ey) break; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (g[nx][ny] #) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; q.push(make_pair(nx, ny)); } } cout dist[ex][ey] endl; return 0; }几个关键点memset(dist, -1, sizeof(dist))对 int 数组可以放心用-1 的补码是全1memset 按字节填充效果是正确的。起点和终点坐标在输入时顺手记录不要额外再遍历一遍。牛客的编译器一般支持 C11所以make_pair这种老写法比花括号初始化更保险。如果你想用auto [x, y]结构化绑定需要 C17 支持有些老编译器会报错不推荐在比赛环境使用。3.2 Python实现deque与二维数组初始化Python 版本更短但有几个坑必须提醒import sys from collections import deque def solve(): n, m map(int, sys.stdin.readline().split()) g [list(sys.stdin.readline().strip()) for _ in range(n)] sx sy ex ey 0 for i in range(n): for j in range(m): if g[i][j] S: sx, sy i, j elif g[i][j] E: ex, ey i, j dist [[-1] * m for _ in range(n)] dist[sx][sy] 0 q deque([(sx, sy)]) dirs ((1, 0), (-1, 0), (0, 1), (0, -1)) while q: x, y q.popleft() if x ex and y ey: break for dx, dy in dirs: nx, ny x dx, y dy if 0 nx n and 0 ny m and g[nx][ny] ! # and dist[nx][ny] -1: dist[nx][ny] dist[x][y] 1 q.append((nx, ny)) print(dist[ex][ey]) if __name__ __main__: solve()第一个坑二维数组初始化千万不要写[[-1] * m] * n。这样看起来没错但实际上每一行都是同一个列表对象的引用修改dist[0][0]会导致dist[1][0]、dist[2][0]全部被修改调试时极其诡异。必须用列表推导式[[-1] * m for _ in range(n)]。第二个坑Python 里deque的popleft()是 O(1) 的如果你贪方便用pop(0)操作普通 list复杂度是 O(n)在大地图上会非常慢。记住BFS 在 Python 里一定要用collections.deque。第三个坑输入处理。牛客的在线评测有时会有空行sys.stdin.readline().strip()会返回空字符串可能导致list()变成空列表。稳妥做法是判空跳过不过这道题通常数据规范不判也能过。3.3 Java实现Queue接口与int[]数组Java 版本在牛客上也很常见这里给一份import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(), m sc.nextInt(); char[][] grid new char[n][m]; int sx 0, sy 0, ex 0, ey 0; for (int i 0; i n; i) { String s sc.next(); for (int j 0; j m; j) { grid[i][j] s.charAt(j); if (grid[i][j] S) { sx i; sy j; } else if (grid[i][j] E) { ex i; ey j; } } } int[][] dist new int[n][m]; for (int i 0; i n; i) { Arrays.fill(dist[i], -1); } int[] dx {-1, 1, 0, 0}; int[] dy {0, 0, -1, 1}; Queueint[] q new LinkedList(); q.offer(new int[]{sx, sy}); dist[sx][sy] 0; while (!q.isEmpty()) { int[] cur q.poll(); int x cur[0], y cur[1]; if (x ex y ey) break; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (grid[nx][ny] #) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; q.offer(new int[]{nx, ny}); } } System.out.println(dist[ex][ey]); } }Java 版有几个细节Queueint[] q new LinkedList()是标准写法ArrayDeque也可以但不要用ArrayList当队列用因为移除头部元素是 O(n) 的。Scanner 读入字符串用next()而不是nextLine()因为nextLine()在读取上一行的换行符时会出问题导致第一行读到空字符串。Java 的二维数组默认值是 0所以需要显式填充为 -1。用Arrays.fill(dist[i], -1)逐行填充是最简洁的写法。三种语言我都提交过实测 C 最快Python 最省事Java 居中。日常练习选哪个都行面试时建议至少掌握 C 或 Java 中的一种因为部分面试官会要求手写代码Python 虽然写起来快但有些人会觉得不够“工程”。4. 迷宫题的进阶玩法4.1 带钥匙和门的迷宫状态压缩BFS走迷宫这道题在牛客上还有很多变体最经典的是加上钥匙和门。地图里会出现a、b、c等多把钥匙和对应大写字母门只有拿到钥匙才能通过对应的门。这时候普通的 BFS 就不行了因为同一个格子在不同钥匙状态下能走的路不一样。解决办法是状态压缩 BFS。用一个整数的二进制位表示当前拥有哪些钥匙比如二进制第 0 位为 1 表示有 a 钥匙第 1 位表示有 b 钥匙。搜索状态从二维(x, y)变成三维(x, y, keyMask)。核心扩展逻辑变成这样for 四个方向: nx, ny x dx[k], y dy[k] if 越界或撞墙: continue if 当前格是大写字母门 and (keyMask 没有对应钥匙): continue 如果当前格是小写字母钥匙: 新状态 keyMask | (1 对应位) 否则: 新状态 keyMask if dist[nx][ny][新状态] -1: 入队visited 数组也要变成三维的dist[x][y][keyMask]。如果钥匙种类是 k总状态数是 n×m×2^k。因为 k 通常不超过 10所以复杂度 O(n×m×2^k) 也还能接受。这种题考察的就是你能不能想到把额外状态压缩进一个整数面试里出现的概率不低。4.2 多起点多终点多源BFS另一种变体是地图里有多个起点或需要求每个格子到最近起点的距离。比如一个迷宫里有很多个出口E求每个空地到最近出口的距离这种题就叫多源 BFS。做法很简单初始化队列的时候把所有的出口全部入队dist全部置为 0然后统一进行 BFS。效果等同于虚拟了一个超级起点它到每个出口的距离都为 0。因为 BFS 是按层扩展的每个格子第一次被访问时一定是被最近的出口先“抢到”所以答案依然是最短距离。多源 BFS 理解起来不复杂代码也就改两三行for 所有坐标: if 是出口: q.push(坐标) dist 0这种技巧在许多实际问题里都会用到比如计算一个城市里每个街区到最近地铁站的距离。掌握了以后可以举一反三面试时如果遇到“多个起火点同时蔓延”的模拟题思路完全一样。4.3 输出路径而非步数记录前驱节点如果题目不满足于输出步数要求输出完整路径比如SSDD这种用 UDLR 表示的移动方向就需要在 BFS 过程中记录每个格子的前驱节点。做法也很简单额外开一个二维数组pre[x][y]记录走到(x, y)的是从哪个格子来的。在扩展时pre[nx][ny] x * m y // 把二维坐标压成一维存储搜索结束后从终点回溯到起点把每一步的方向字符拼起来最后再反转一下就是正向路径。注意如果用字符记录方向从(nx, ny)记录方向时要记“从(x, y)到(nx, ny)的方向”。输出路径的题有个常见陷阱BFS 找到的第一条路径不一定字典序最小。如果题目要求字典序最小路径需要调整方向数组的顺序比如按D, L, R, U的顺序扩展保证先搜索到的路径字典序更小。这类细节最容易丢分做题时务必看清要求。5. 高频坑点与调试心得5.1 样例全对、提交WA的几类原因“本地样例都能过一提交就 WA”几乎是每个刷题人都会经历的痛苦。走迷宫这道题WA 的原因翻来覆去就那几个。第一起点或终点被墙壁覆盖。虽然题目通常会保证S和E是合法字符但有些变体里起点旁边一圈全是墙BFS 根本扩展不出去最后 dist 是 -1输出也是 -1这是对的。但如果题目保证一定有解你却输出 -1那就要检查是不是把S或者E当成墙处理了。第二忘记把起点标记为已访问。如果你初始化的 dist 数组全是 -1起点入队前没有设置dist[sx][sy] 0那 BFS 扩展时可能会重新回到起点起点被反复入队。在地图特别大的情况下这不一定会 WA但会超时。第三输入顺序看反。有些题目是先给 m 后给 n或者在每行字符串里带了空格。牛客上的输入一般比较规范但一旦你从别的 OJ 复制代码过来一定要重新确认读入顺序。我吃过一次亏样例里 n 和 m 恰好相等根本测不出来。第四终点判断的位置不对。如果你在出队时才判断是否到终点那答案是准的如果你在入队时就判断if (nx ex ny ey)直接 break那步数需要额外加 1。两种写法都行就怕混着写。5.2 提交超时的排查方向超时主要靠三点排查。第一是不是用了 DFS。我见过不少同学把走迷宫当成 DFS 题做还写了剪枝结果 100x100 的全通路地图直接跑不动。如果你的代码里有递归函数先想想这道题能不能用 BFS 解决。第二是不是标记时机错了。这部分我在 2.2 里已经强调过入队不标记会导致大量重复节点入队队列长度暴涨超时是必然的。第三是不是 I/O 太慢。C 里如果用了cin且没有关闭同步在大数据量输入时会比scanf慢不少。可以加一行ios::sync_with_stdio(false); cin.tie(nullptr);。Python 里如果用了input()而不是sys.stdin.readline()数据量大时也会吃力。这些都是经验之谈平时注意一下能省很多调试时间。5.3 小成本自测与调试技巧刷这种模板题自己写测试用例是基本功。我最常用的方法是手动构造几个边界用例1×1 的格子起点就是终点只有起点和终点的 2×1 格子四面都是墙的孤岛终点以及全通路的大地图。调试时最有用的工具就是打印 dist 二维数组。BFS 结束后把整个 dist 矩阵打出来for i in range(n): for j in range(m): print(f{dist[i][j]:3d}, end) print()看到数字按层次向外扩散说明 BFS 逻辑基本正确。如果出现某个格子被不均匀地赋值或者起点周围数值乱跳那多半是标记时机或方向数组写错了。还有一个很实用的技巧在出队后的终点判断处加一个计数器统计队列弹出总次数。如果弹出次数远大于 n×m说明有重复入队赶紧检查 visited 标记。这个计数器在最终提交前删掉即可。写在最后的小经验走迷宫这个题目我已经不知道写过多少遍了但每次在牛客上遇到它我还是会当全新题去读一遍题面因为变体实在太多了。我个人体会是BFS 模板背熟只是第一步真正拉开差距的是你能不能快速识别“一个格子可以有不同的状态”比如带钥匙、传送门、多起点。这个能力只能靠多刷题喂出来。最近看到牛客上有人聊“长度为3的连续子串”那道字符串题跟走迷宫完全不是一个画风但底层逻辑是一样的先把最朴素的模板写到条件反射再在模板上做加减法。希望这篇拆解能让你以后再看到“走迷宫”三个字心里不慌手上有活。