1. 写在前面其实迷宫题没你想的那么难刷牛客的朋友应该对“走迷宫”这类题不陌生它几乎是每日一题里的常客也是面试笔试里出场率极高的一类搜索题。我见过不少同学一看到“迷宫”两个字就发怵觉得要处理什么高深算法其实剥开外壳看走迷宫问题核心就是一件事在图里找一条从起点到终点的合法路径有时要求最短有时只求可行偶尔还要你输出路径本身。这篇就借着牛客每日一题里的走迷宫题目把这类题从输入处理、状态表示、搜索策略到代码实现完整捋一遍。我会结合自己刷题和实际写代码的经验把那些文档里不写、但考试和面试时特别容易踩的坑也一并交代清楚。适合的人群很明确准备校招笔试的同学、刚接触搜索算法想系统过一遍的新手以及想看明白这类题怎么从“会做一道”变成“会做一类”的进阶选手。这篇文章不会只贴代码然后就完事重点讲每个关键选择背后的为什么。为什么用BFS而不是DFS为什么有些迷宫题必须拆成多个状态来做为什么方向数组的顺序有时会直接影响超时还是AC——这些才是走迷宫题真正的分水岭。2. 题目整体拆解先搞懂迷宫题到底在考什么2.1 从题面提炼三个关键约束拿牛客上典型的走迷宫题目来看题面一般会给你一张地图用字符或数字表示其中包含起点、终点、墙壁和空地。比如常见的形式是S表示起点E表示终点#表示墙.表示可走的路。听起来很简单但把题面翻译成算法问题需要拆出三个部分第一个是图模型的建立。迷宫本身就是一个二维网格每个格子是节点上下左右相邻的可通行格子之间连一条边。这个建模过程看起来基础但很多人写代码时根本没有显式建模的意识只是拿着二维数组直接处理这没问题但脑子里必须有“这是一张图”的认知否则后面的搜索策略无从谈起。第二个是移动规则。绝大多数走迷宫题只允许上下左右四个方向移动但有些变种会加八连通、允许斜着走甚至允许“跳跃”“传送”等特殊动作。移动规则直接决定方向数组怎么设计和状态怎么扩展这是第一个容易出问题的地方。第三个是求解目标。题目问“最少走几步”“能否到达”“输出一条路径”还是“有几种走法”对应的算法完全不同。牛客每日一题里的走迷宫最常见的问法是求最短步数这基本就锁定了BFS。少数题目会问能否到达这时DFS也能做但要注意 DFS 在最坏情况下可能退化得很慢如果题目卡时间就得谨慎。2.2 为什么说BFS是迷宫题的第一默认解迷宫题求最短路径第一反应就该是BFS这是有理论依据的。BFS按层扩展从起点出发先访问距离为1的所有节点再访问距离为2的所有节点以此类推。由于队列先进先出的特性第一次访问到终点时这条路径一定就是最短的。DFS也能找路径但它在找最短路径时需要枚举所有可行路径才能比较长度复杂度是指数级的在稍大的迷宫上根本跑不动。而BFS的复杂度是 O(V E)V是节点数E是边数在二维网格里也就是 O(行数 × 列数)。这个复杂度表现让BFS几乎成了迷宫最短路径问题的标准答案。不过BFS有个特点容易忽略它只能求最短步数如果要输出路径需要另外记录前驱节点。这个延伸我在后面的实操部分会专门演示。2.3 不是所有迷宫题都只开一个visited数组基础版本的迷宫题一个二维visited数组就够了标记哪些格子已经走过。但很多题目会在迷宫基础上加状态。牛客上有不少走迷宫变种比如“有几把钥匙才能开门”“走到某个位置后多一个跳跃技能”“踩到机关后地图会变化”等等。一旦出现这些扩展条件单纯用二维数组记录“这个格子来过没有”就不够了因为同一个格子在不同的状态下后续能走的路完全不一样。这时候需要把状态扩展成(x, y, state)三元组state表示当前持有的特殊状态比如钥匙集合的位压缩值。visited数组也得对应升级成三维数组否则会漏解。这类扩展虽然看起来复杂但理解“状态就是BFS的节点”这句话之后就能一通百通。本文后面的题解会先演示标准版再给出一个带额外状态约束的版本的思路帮助大家真正吃透。3. 标准版走迷宫题解从输入到输出全流程3.1 输入处理的细节与陷阱先看一段标准版题目的代码骨架我用 Python 写因为刷题和面试手撕时 Python 表达起来最清晰。from collections import deque def solve(): n, m map(int, input().split()) grid [] for i in range(n): row input().strip() grid.append(row) if S in row: sx, sy i, row.index(S) if E in row: ex, ey i, row.index(E)这段代码看起来平平无奇但有几个细节值得强调。第一input().strip()不能省。牛客和一些OJ平台的输入行末尾可能带回车甚至空格不strip直接处理字符比对的时候很容易因为\r或空格导致匹配不上。别笑我真见过有人在这上面卡了半小时。第二row.index(S)一次只能找到一个起点如果迷宫里有多个S这行代码会直接报错或者找到错误的位置。题目一般会保证起点唯一但如果自己出数据测试最好写一个遍历所有格子的循环来统一起点和终点坐标更稳。第三迷宫规模。日常题目的 n 和 m 通常是 10 到 1000 之间但有些题会到 2000 × 2000。这时候如果读入用[[0]*m for _ in range(n)]这样建二维数组内存是扛得住的但如果你习惯用嵌套列表逐行append要注意每一行其实是一个字符串直接grid[x][y]取出来的是字符而不是数字别下意识去和整数比较。这里补充一个经验如果题目给的地图是用0/1表示空地/墙壁我会习惯把0记为可走、1记为墙然后读进来转成整数二维数组如果是字符地图就直接用grid[x][y] #判断。不要中途混用越简单越不容易错。3.2 BFS核心代码与每行注释下面是核心的BFS搜索部分我把它拆成几个小函数来写面试手撕的时候结构更清晰。from collections import deque def bfs(grid, n, m, sx, sy, ex, ey): dist [[-1] * m for _ in range(n)] # dist同时充当visited数组-1表示未访问过 dist[sx][sy] 0 # 方向数组右、下、左、上 dx [0, 1, 0, -1] dy [1, 0, -1, 0] q deque() q.append((sx, sy)) while q: x, y q.popleft() if x ex and y ey: return dist[x][y] for i in range(4): nx, ny x dx[i], y dy[i] if 0 nx n and 0 ny m and grid[nx][ny] ! # and dist[nx][ny] -1: dist[nx][ny] dist[x][y] 1 q.append((nx, ny)) return -1 # 无法到达仔细看这段代码里的几个设计决策。第一dist数组初始化全为 -1这个设计很妙。它同时承担了两个职责一是标记是否访问过避免死循环二是记录步数。当dist[nx][ny] -1时说明还没访问过此时给它赋dist[x][y] 1一步到位不需要单独开一个visited数组。很多教材里是visited和dist分开写逻辑更直观但合并写更省事而且在有些语言里还能省点内存。第二方向数组的顺序。我写的是右、下、左、上。有些同学会问顺序有没有讲究。对于求最短步数的标准BFS顺序不影响答案的正确性但会影响搜索路径和入队顺序。如果题目要输出路径方向数组的顺序可能影响你最终输出的那条路径长什么样。顺序无所谓但要保证四个方向完整别漏方向——有人为了优化只写两个方向理由是只能向右向下走这在部分题目里是成立的但题目没说就不能乱剪。第三边界检查0 nx n and 0 ny m必须在访问grid[nx][ny]之前做。Python的and是短路求值所以把边界检查放前面索引越界就不会发生。反过来写grid[nx][ny] ! # and 0 nx n下一个坐标越界时前面的条件已经访问了非法索引直接抛异常。这个顺序问题是新手写BFS时最经典的报错来源。第四终点检查放的位置。我放在pop之后检查也就是“处理当前节点时判断是不是终点”。另一种写法是在入队前检查那样可以少扩展一层稍微快一点。但入队前检查有个小坑如果起点就是终点入队前检查会在起点入队那一瞬间就返回逻辑上没问题但如果把检查放在pop后起点也会被正常处理。两种都行我偏向pop后检查因为代码更统一不容易漏特殊情况。3.3 完整代码和样例测试把上面的函数组装成完整可提交的代码from collections import deque def bfs(grid, n, m, sx, sy, ex, ey): dist [[-1] * m for _ in range(n)] dist[sx][sy] 0 dx [0, 1, 0, -1] dy [1, 0, -1, 0] q deque([(sx, sy)]) while q: x, y q.popleft() if x ex and y ey: return dist[x][y] for i in range(4): nx, ny x dx[i], y dy[i] if 0 nx n and 0 ny m and grid[nx][ny] ! # and dist[nx][ny] -1: dist[nx][ny] dist[x][y] 1 q.append((nx, ny)) return -1 def solve(): n, m map(int, input().split()) grid [] sx sy ex ey -1 for i in range(n): row input().strip() grid.append(row) for j, ch in enumerate(row): if ch S: sx, sy i, j elif ch E: ex, ey i, j result bfs(grid, n, m, sx, sy, ex, ey) print(result) if __name__ __main__: solve()拿一个简单样例测一下输入 5 5 S.... ###.# ...#. .##.# ....E这个迷宫里起点在(0,0)终点在(4,4)。手动推一下路径从(0,0)往下走到(1,0)不行因为(1,0)是#往右到(0,1)一路往右到(0,4)然后往下绕过墙壁最终能到达。用上面的代码跑输出应该是8。我为什么特意选这个样例因为它在第2行中间有一个单独的空地夹在墙之间看起来像死路实际上走法只有一条容易手算验证BFS的正确性。4. 进阶扩展状态压缩与条件约束4.1 当迷宫不只是迷宫带上钥匙和门的版本牛客上有一类迷宫题比基础版高一个台阶地图里有钥匙和对应的门必须捡到钥匙才能通过门。这时候如果还用二维visited同一个格子可能被走两次——第一次没有钥匙经过它没意义第二次带着钥匙经过它才能开门。这两种情况对后续路线的影响完全不同。解决办法是把BFS的节点从(x, y)扩展成(x, y, key_mask)。比如地图里最多有k种钥匙key_mask的第i位是1表示已经捡到了第i把钥匙。用一个三维visited数组vis[x][y][1 k]来记录状态是否走过。from collections import deque def bfs_with_keys(grid, n, m, sx, sy, ex, ey, key_id): # key_id 是一个字典记录钥匙字符 - 编号 # vis[x][y][mask] 表示在(x,y)位置且持有钥匙集合为mask时是否访问过 vis [[[False] * (1 len(key_id)) for _ in range(m)] for _ in range(n)] dx [0, 1, 0, -1] dy [1, 0, -1, 0] q deque() q.append((sx, sy, 0)) vis[sx][sy][0] True steps 0 while q: size len(q) for _ in range(size): x, y, mask q.popleft() if x ex and y ey: return steps for i in range(4): nx, ny x dx[i], y dy[i] if 0 nx n and 0 ny m and grid[nx][ny] ! #: # 遇到门但没有对应钥匙时跳过 if grid[nx][ny] D: door_id ... # 根据地图布局确定门编号 if not (mask door_id) 1: continue new_mask mask if grid[nx][ny] in key_id: new_mask | (1 key_id[grid[nx][ny]]) if not vis[nx][ny][new_mask]: vis[nx][ny][new_mask] True q.append((nx, ny, new_mask)) steps 1 return -1注意这里我用size len(q)分层遍历steps是当前层的步数这样搜到终点直接返回steps不需要在节点里再存dist字段。分层BFS在需要输出“按层信息”的题里非常有用比如求到达某个区域的最少步数、或者要记录每层有多少个节点的时候。这里我给的是一个带钥匙门的典型模板。实际题目千变万化但核心思想只有一个把题目里所有影响移动决策的因素全部编码进状态里然后在这些状态构成的图上做BFS。我见过不少同学在这个思路上绕不出来总觉得BFS只能在原地图上做其实状态扩展之后每个(x, y, mask)都是一个独立节点图的规模就是n * m * 2^k在n,m≤100, k≤10时完全跑得动。4.2 不加visited会怎样死循环与指数爆炸写DFS或BFS时不加visited或者visited状态维度不够最直接的后果是死循环。把vis[nx][ny][new_mask]去掉你会发现同一个状态会被反复入队从起点走到钥匙 A捡到钥匙后再绕回来又经过同一个格子又捡一次钥匙然后继续绕直到队列无限膨胀。这不是危言耸听我在实际调题时真的遇到过。那次是一个带传送门的迷宫传送门会把角色传送到另一个点我偷懒只记录了(x,y)以为传送门不会造成状态循环结果程序跑了几分钟还没结束。排查后发现问题传送点之间来回传visited每次都不同实际上无限循环。把状态扩成(x, y, current_state)之后问题立刻解决。这说明一个通用的经验只要状态转移图中可能出现环就必须有去重机制去重的粒度必须和状态的定义一致。你用三维状态就得用三维visited你用二维状态就别去访问三维的vis[x][y][0]然后自欺欺人以为记录全了那会漏状态导致答案错误。4.3 话说回来热词“长度为3的连续子串”与走迷宫的关系搜索热词里有一条“牛客长度为3的连续子串”很多同学可能觉得和迷宫八竿子打不着但它其实揭示了一个很重要的刷题现象牛客的每日一题会在不同算法专题之间轮换有时候一道题会同时融入字符串处理和搜索两个考点。举例来说一种是地图上每个格子是一个字符路径经过连续3个格子会形成一个长度为3的子串题目要求统计所有从起点到终点的路径中出现次数最多的长度为3的子串。这种题就是BFS 滑动窗口/哈希计数的组合。另一种牛客上出现过的变体是迷宫路径的方向序列不能出现某种长度为3的连续模式比如“不能连续向右两次再向下”这相当于给路径状态加了记忆需要用(x, y, last_action1, last_action2)四个维度来记录最近两步的移动方向才能保证扩展时不会生成非法路径。这类“题面缝合”是近几年笔试出题的一个趋势但不管题面怎么变底层还是搜索。所以我建议刷走迷宫题的时候多想想同一个代码框架换个条件还能解什么题这种“迁移力”比多刷十道重复题都管用。5. 路径输出从最短步数到完整路径5.1 使用前驱节点回溯路径很多迷宫题进阶一步就问“输出最短路径”。BFS本身只能告诉你最短步数要输出路径就得记录每个节点是从哪个节点扩展过来的。通常用prev字典或二维数组来存前驱def bfs_with_path(grid, n, m, sx, sy, ex, ey): dist [[-1] * m for _ in range(n)] prev [[None] * m for _ in range(n)] # 每个格子存 (prev_x, prev_y) dist[sx][sy] 0 dx [0, 1, 0, -1] dy [1, 0, -1, 0] q deque([(sx, sy)]) while q: x, y q.popleft() if x ex and y ey: # 回溯路径 path [] while (x, y) ! (sx, sy): path.append((x, y)) x, y prev[x][y] path.append((sx, sy)) path.reverse() return path for i in range(4): nx, ny x dx[i], y dy[i] if 0 nx n and 0 ny m and grid[nx][ny] ! # and dist[nx][ny] -1: dist[nx][ny] dist[x][y] 1 prev[nx][ny] (x, y) q.append((nx, ny)) return None这里有几个关于回溯的讲究。第一prev记录的是“从哪个格子来”不是“到这个格子去”顺序反了回溯就会乱。第二回溯完成后要reverse()因为从终点往起点倒着取取出来是逆序的路径。第三path里存的是坐标元组如果要输出“S . . # E”这样的字符路径可以在地图副本上把对应坐标改成*之类标记再按行打印。5.2 为什么回调用DFS的总是你我遇到过不少同学在走迷宫题里下意识用DFS因为“顺着一条路走到底再换路”的感觉很自然递归写起来也很短。但问题在于DFS天然适合的是“是否存在路径”和“枚举所有路径”的场景它得到的解不保证最短。如果题目要求最短路径DFS也可以做但要把所有路径都走完才能比较这在迷宫规模稍大一点就是个灾难。而且函数的递归层数还会受递归栈深度限制Python默认递归深度是1000迷宫如果超过1000行直接出RecursionError。这在笔试题里不算罕见所以我现在养成一个习惯只要能BFS绝对不DFS。只有在题目明确要求“输出任意一条可行路径”且图非常大、BFS空间不够或题目结构特殊比如拓扑排序类搜索时才考虑用DFS。顺带提一个“BFS求最短路径为什么不能记步数后直接写DFS”的常见误区。有人会想先用BFS算dist然后写一个DFS只沿着dist递减的方向走是不是也能拿到最短路径答案是可以这种技巧叫“在最短路径DAG上DFS”乍一看高效但实现起来比直接记录prev容易出bug因为你需要保证每条向下走的边都严格减少步数稍不小心就会被绕晕。6. 常见问题与排错速查6.1 从超时到答案错七个高频坑位我把自己在牛客和线下笔试中遇到过的、以及帮人debug时见到最多的问题整理了一下。很多问题不是思路不会而是细节踩坑。第一个坑输入读取错误。地图行的strip()没写导致每行尾部的\r混进去grid[nx][ny] #永远比不中起点终点也找不到。表现是样例能过一部分复杂样例全部报错。排查方法打印读入的grid看每行末尾是不是多了字符。第二个坑分隔符和索引混淆。有人喜欢把(i, j)和(x, y)混用坐标顺序写反。地图行数是n、列数是m访问是grid[x][y]x对应行y对应列。但从row.index(S)拿到的y是列坐标赋值时sx i, sy j方向数组里dx控制行变化、dy控制列变化。任何一个搞混搜索就会“穿墙”或者方向走反。第三个坑visited标记的时机。BFS里有人把标记放在pop之后而不是入队时会导致同一节点被重复入队。比如一个格子先从起点扩展两次第二次入队时没标记后面还会被第三次扩展。结果就是队列膨胀、超时、甚至答案错误。正确做法是入队即标记这样每个节点最多入队一次。第四个坑边界条件用还是。以0 nx n这种写法最好一旦写成0 nx n就有一行越界访问等着你。这类错误在Python里有时不报错而是返回错误结果特别坑。第五个坑终点不可达时返回值忘写。BFS循环结束后没有return -1函数隐式返回None如果外层代码直接用这个值和数字比较报TypeError。这类错误让人看着一头雾水其实是结束条件没写全。第六个坑坐标被墙挡住但提前终点判断。有些迷宫终点是E但它旁边的格子全是墙只有起点方向能进来这没问题。但如果终点被墙围死BFS永远搜不到它循环结束后返回-1还是None就取决于上面第五条。写题前先看题目要求不可达时输出什么别习惯性写-1。第七个坑嵌套列表初始化共享引用。Java/C选手转Python容易遇到dist [[-1] * m] * n这样建出来的二维数组每一行都是同一个对象的引用。改一行会影响所有行。正确写法是[[-1] * m for _ in range(n)]。别小看这个我之前调试一个多源BFS题整整多花了十分钟才发现是这里的问题。6.2 调试迷宫题的三个实用技巧第一个技巧是小规模暴力验证。给BFS和DFS各写一个实现在 5×5 的小迷宫里随机生成障碍对比两个版本的输出。DFS保证每种可达路径都能找到所以如果BFS输出-1而DFS说可达那问题多半在BFS的 visited 逻辑或边界检查上。第二个技巧是打印搜索轨迹。在pop出来的节点上打印(x, y)再把搜索顺序和你手动模拟的顺序对照。如果搜索顺序忽前忽后说明方向数组写错了。这个方法在调试带钥匙门的题目时尤其管用因为钥匙状态的变化打印出来一眼就能看出有没有漏捡。第三个技巧是用deque而不是list.pop(0)。用list.pop(0)模拟队列每次弹出都要移动整个列表的元素时间复杂度是 O(n)在数据大的时候直接超时。这个坑排除了代码逻辑问题之后往往是性能瓶颈的大头。6.3 一个让我印象深刻的debug实录去年我在牛客上刷一道带钥匙的迷宫题本地测试样例全过一提交就超时。检查逻辑没问题visited也开了三维想了很久。后来定位到问题我数了一下钥匙种类地图里可能有 10 把钥匙而1 10是 1024 种状态乘上 500×500 的地图数组规模是 2.5 亿个布尔值。Python 里这一个数组就占了几百MB内存初始化就要花好几秒不超时才怪。后来我改用字典来存访问状态vis set()里面存(x, y, mask)三元组只有真正访问过的状态才会被加入内存大幅下降提交直接通过。这个经验之后我养成了习惯在大规模地图、多状态题目里优先用set而不是高维数组。当然这带来一点性能开销Python 里 set 的读写是 O(1) 期望复杂度绝大多数场景足够用。如果你纠结性能和内存的平衡还有一个技巧是先把状态压缩成整数比如state (x * m y) k | mask然后存进set。这样存储和比较都比三元组小一点在状态特别多时也能快一截。不过日常刷题三元组直接存set已经够了别过度优化。7. 从每日一题到一类题刷题复盘的正确姿势7.1 我的复盘模板牛客每日一题往往只给一道题和题解很多同学把AC当成终点代码一提交就关掉页面下次遇到同类型题还是不会。我从自己做编程题的经验来看题解只是起点真正产出能力的是复盘。我一般会按这个模板走一遍这题用了什么算法和数据结构如果题目改一个条件比如允许斜着走、加一个时间限制、要求输出所有最短路径代码要怎么改我在哪一步卡住了是流程不熟还是某个API忘了能不能给自己出一道变体题然后不看题解敲出来比如说标准走迷宫AC了我就给自己加要求改输出路径再加要求地图里有钥匙和门再加要求终点不是唯一目标要收集齐若干宝物才算结束。每加一个要求本质上都是在改BFS节点的状态定义和转移规则反复练几道之后你会发现所有搜索题都变成了同一个套路。7.2 把“牛客长度为3的连续子串”这类热词用起来搜索热词“牛客长度为3的连续子串”让我想到刷题时一个容易被忽略的现象很多题目的名字和考点之间联系是跳跃的你只看标题想象不出来它要干什么。比如“走迷宫”听起来只是搜索题但唯一天然衔接的子串考点可能就是迷宫路径逐格形成的字符串衍生问题。这类融合题的解题顺序讲究从外到内。先剥掉外壳找到“核心数据结构是图”这一点再看附加条件里需要维护什么额外信息是最近几个字符、是持有的钥匙集合、还是已走过的步数奇偶性最后据此决定BFS节点的状态维度。关键词的作用不是让你背下来而是帮你建立索引。刷题多了你一看“连续子串”就知道可能要和哈希/滑动窗口结合一看“迷宫”就知道搜索。但是别被关键词带偏该做的建模依然要做状态、目标、转移规则一个都不能少。8. 写在最后的个人心得走迷宫题我前前后后刷了不下三十遍包含各种变体从最简单的二维BFS到带状态压缩的钥匙门迷宫再到带方向记忆的子串约束迷宫。我的体会是这类题最大的价值不在于让你记住BFS的代码而在于训练一种“把实际问题抽象成图”的思维方式。有一次我和朋友开玩笑说走迷宫题的代码翻来覆去就是那几行方向数组、边界检查、入队标记、终点判断。但我见过太多人栽在“终点判断放哪”“visited什么时候置位”“状态维度够不够”这些细节上。这些细节写起来只是一两行代码的差别背后却是对搜索本质的理解深度。最后分享一个小技巧是我在笔试前突击时总结的。每次拿到一道搜索题先别急着写代码在纸上画一个 3×3 的最小迷宫把起点终点和障碍摆好然后手动模拟一遍BFS的队列变化。这个 10 秒钟的习惯能帮你提前发现一半以上的逻辑错误。我靠着这个小动作在好几次笔试里避免了一提交就是WA的尴尬。希望这篇关于牛客每日一题“走迷宫”的拆解能帮到你。如果你最近正在刷这类题不妨现在就把这篇文章里的标准版代码敲一遍然后自己加一个“输出路径”的要求看看能不能顺利跑通。能跑通说明你是真的懂BFS了。