刷算法题刷到一定阶段你会发现摆在面前的东西其实就那几类数组、链表、二叉树再往后就是网格图BFS这一类避不开的题型。你去力扣或者洛谷上翻凡是给你一个二维网格让你求最短步数、统计岛屿数量、模拟病毒扩散面积的题十有八九都是同一套解法。我最早接触这类题的时候也写得稀烂不是队列里塞错对象就是visited标记晚了一步导致死循环后来把套路彻底拆了一遍发现这些题底子都是同一个模板。这篇就把我拆出来的东西完整讲一遍给正在刷算法题、尤其是卡在网格题上的朋友一份可以直接照抄的作业。模板这东西理解透了随便变理解不透背下来也没用。所以我不光给你代码还会把每一步设计背后的原因讲清楚包括BFS为什么能保证最短、visited为什么必须在入队时标记、方向数组该怎么设计。看完之后你应该能做到碰到任何网格图题目先判断能不能用BFS能的话直接套框架再把题目独有的条件塞进去。1. 网格图为什么是BFS刷题的主战场1.1 先用图论的眼光看二维数组大多数人对二维数组的第一印象是一个表格下标取它值存着。这种印象在遍历打印的时候没问题但在算法题里会挡住你看穿本质所谓的网格图实际上就是一张图。二维数组的每个格子是一个节点每个节点通过上下左右四条边连接到相邻格子。边权是多少从A格子走到相邻的B格子只需要一步所以边权恒为 1。这就构成了一张无权图。图论里有个结论在无权图上求最短路BFS是首选因为它逐层扩展第一次到达某个节点时走过的路径就是最短路径。网格图正好命中了BFS最擅长的场景。理解了这层对应关系之后很多题就不再是模拟题了而是图论题。比如力扣 200 岛屿数量本质是求图的连通分量个数力扣 994 腐烂的橘子本质是多源最短路力扣 130 被围绕的区域本质是从边界出发的反向遍历。题目披着数组的外衣内核全是图的算法。1.2 网格图为什么天然适配BFS在树结构里我们经常用递归做DFS因为树的分支结构很规则栈的深度能接受。但网格图不一样它的分支天然就是四个方向而且是平面扩散而不是向下生长。用DFS递归处理一个 200x200 的全连通网格递归深度在最坏情况下可能达到 40000 层直接栈溢出用BFS队列则完全没有这个问题队列的空间复杂度是 O(mn)但不会因为递归深度爆栈。还有一个关键点是层级性。BFS每次从队列里取出一整层节点再扩展出下一层这种层的概念对应到网格图上就是走了几步。你要算最短步数BFS天然就能在第一次碰到目标时返回结果而DFS会一条路走到黑你很难知道目前走的是不是最短的必须回溯比较所有路径。所以从算法和工程两个角度看网格图上的求解问题用BFS都更合适。你还会在题解区看到很多人用DFS做岛屿题因为连通块问题DFS也能做而且代码写起来更短。但我的建议还是练熟BFS一是BFS的逐层思路在更多题型里通用二是面试时讲BFS的扩散过程比讲DFS的递归回溯更容易让面试官跟上你的思路。2. 一套能吃遍大多数题的BFS模板怎么写2.1 标准模板代码先给出一套我一直在用的网格图BFS模板语言是Python。这套模板覆盖了 90% 的网格图题目后面所有题型都会从它演化。from collections import deque def bfs_grid(grid, start, target): if not grid or not grid[0]: return -1 m, n len(grid), len(grid[0]) visited [[False] * n for _ in range(m)] directions [(1, 0), (-1, 0), (0, 1), (0, -1)] q deque([start]) visited[start[0]][start[1]] True steps 0 while q: size len(q) for _ in range(size): x, y q.popleft() if (x, y) target: return steps for dx, dy in directions: nx, ny x dx, y dy if 0 nx m and 0 ny n and not visited[nx][ny]: # 这里根据题目条件过滤障碍物等 visited[nx][ny] True q.append((nx, ny)) steps 1 return -1这套模板的核心思路是队列维护当前层的所有节点每一轮循环处理一层处理完一层步数加一。起点入队时立刻标记visited保证同一个格子不会被重复塞进队列。2.2 模板里几个设计决策的为什么先回答一个高频问题为什么用collections.deque而不是 Python 内置的 list因为BFS需要从队头弹出元素list 的pop(0)时间复杂度是 O(n)每次弹出都要把后面的元素整体前移。在网格巨大、节点入队次数多的时候这个开销会明显拖慢程序。deque 的popleft()是 O(1)翻页之间就能完成。然后是这题最关键的一个点为什么必须在入队时标记visited而不是出队时再标记如果我们在popleft()之后才标记会有一个致命问题某个格子可能被多个邻居同时发现在它还没被弹出之前其他邻居又会把它再次入队。结果就是同一个节点在队列里出现好几份在大网格上队列长度会膨胀好几倍严重时会直接超时。入队即标记从源头上保证了每个格子最多入队一次这是BFS不超时的基石。再解释一下size len(q)这行的用途。BFS有两种写法一种是队列里只存节点不知道当前在第几层另一种是每次先取出当前层的大小然后只处理这么多节点这样层与层之间就有明确边界。做最短路径类题目时需要返回步数size就是为这个服务的。如果你只是要求遍历全部节点或者统计连通块大小也可以不按层处理直接 while q 循环即可但要统计步数就必须分层。2.3 模板变体路径记录、多源起点与障碍过滤实战中模板还有几个高频变体。第一种是记录路径。最短路径类题目有时不只要步数还要你输出路径。此时可以在visited之外增加一个prev二维数组记录每个格子是从哪个格子走过来的。找到目标后从目标往回回溯prev数组就可以还原完整路径。代价是额外 O(mn) 的空间但思路很直观。第二种是多源起点。有些题一开始就有多个起点比如腐烂的橘子里所有初始腐烂的橘子都能向外传染。解法很简单初始化队列时把所有起点一起append进去全部标记visited然后正常BFS。多源BFS的层数含义依然正确因为它本质上是从多个口同时注水水位按同一速度上涨。第三种是障碍和条件的过滤。模板里我在扩展方向前加了一个注释根据题目条件过滤障碍物。这个条件千变万化可能是grid[nx][ny] #跳过可能是只允许走数字更大的格子也可能是奇偶性限制。无论条件多复杂位置都固定在扩展邻居之后、入队之前。这个位置的选择很讲究——先判断坐标是否越界再判断是否访问过最后用题目条件筛掉不可走的格子。顺序反了轻则访问无效坐标重则下标越界抛出异常。3. 方向数组与visited标记最难察觉的坑都在这3.1 方向数组的写法与选择网格图BFS的扩展说白了就是上下左右四个方向。我见过三种写法# 写法一两个平行数组老式C风格 dx [-1, 1, 0, 0] dy [0, 0, -1, 1] # 写法二方向元组列表更 Pythonic directions [(-1, 0), (1, 0), (0, -1), (0, 1)] # 写法三循环里手写四个 if唯一优势是直观不推荐我个人推荐写法二因为它把方向打包成一个个元组循环里for dx, dy in directions直接拆包一眼就能看出你在遍历四个方向。写法一的逻辑等价但两个数组的距离感强一些写错下标的时候也不好查。需要注意一个方向数组的坑dx是行的偏移dy是列的偏移。处理行的时候用x dx处理列的时候用y dy千万别混。很多题解里坐标写成(row, col)这时 row 对的就是 xcol 对的就是 y。我见过有人把行偏移加到列上去结果整个遍历路线变成斜线最后在角落死循环排查了半天才发现方向数组和坐标别名对应错了。方向数组还承担着扩展方向的可变性。有的题要求可以斜向移动那就把八个方向全部列出来directions [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]有的题模拟的是国际象棋骑士的走法方向数组就是那八个日字位移。方向数组只是数据怎么走永远由题目说了算。把方向数组从四个 if抽象成一组方向代码的适配性会好很多。3.2 visited标记的两个高频Bug第一个Bug是延迟标记。我在第 2 节说过出队时标记会让节点重复入队。这里我可以给你一个具体的反例在 3x3 网格上起点 (0,0) 入队后它的邻居 (0,1) 和 (1,0) 入队。下一层处理 (0,1) 时会发现 (1,1) 和 (0,2) 还没标记入队。但注意(1,0) 在旁边同时也会发现 (1,1)如果 (1,1) 还没被访问它又会入一次队。也就是说同一个格子 (1,1) 在队列里出现了两份。一旦网格变大这种重复入队是指数上涨的时间直接爆炸。第二个Bug是visited数组的维度设计。绝大多数题用二维布尔数组就够了但也有些题要求你在状态空间里BFS此时visited的维度要跟上状态。比如在网格里走迷宫同一个格子走过一次之后不能再走第二次和同一个格子可以走多次但剩余步数不同是完全不同的题目。后者需要visited[x][y][rem]三维标记否则会把中间状态丢掉而漏解。刷题时看到状态二字就提醒自己 visited 要不要加维度。还有一个实操技巧如果题目允许修改原数组可以用原地标记替visited。比如在网格里把已经访问过的格子值改成#或-1下次扩展时发现这个值直接跳过。这样做空间复杂度降到 O(1)在面试时是个加分项。但要注意只有当你确认原数组的值后续不需要再被读取时才可以用。像被围绕的区域这类需要保留原值的题就不能随便改。3.3 边界判断的先后顺序边界判断是网格题最容易翻车的环节。标准写法是if 0 nx m and 0 ny n and not visited[nx][ny]:注意not visited[nx][ny]一定放在0 nx m and 0 ny n之后。Python 的判断是短路求值的前者为 False 时根本不会执行后面的visited[nx][ny]所以顺序对了不会越界。如果你把顺序写反当nx越界为负时visited[-1][ny]能取到东西——它在 Python 里不会报错但返回的是最后一行数据逻辑全乱了。这种问题出现的时候极其隐蔽你以为BFS在工作实际上在访问那些根本不该出现的幽灵格子。另一个容易忽略的判断点是起点本身就不可达。如果起点在障碍物上或者起点就是终点模板里的初始检查要放在入队之前。我在模板开头特意写了if not grid or not grid[0]这行看似简单却在网格题里救过我好几次——空网格直接访问grid[0]会抛异常不检查的话还没进入BFS就已经崩了。4. 高频题型拆解从岛屿到多源扩散怎么套模板4.1 连通块计数从岛屿数量开始力扣 200 岛屿数量是网格图BFS的入门题也是无数人写第一道网格题的地方。题目给一个1陆地和0水组成的二维网格让你统计岛屿数量。所谓岛屿就是被水包围的连通的陆地。你只要遍历整个网格遇到一个未被访问的1岛屿计数加一然后以这个格子为起点做一次BFS把整个连通块里所有相邻的1全部标记为visited。遍历完整个网格后计数就是答案。这里套模板时有一个优化点遍历顺序和BFS的结合。常规做法是外面套两层 for 循环里面根据条件启动BFS。注意BFS启动后它会把当前岛屿的所有格子标记掉外层循环在后续遍历时就不会再碰到这同一个岛屿了。所以每个格子最多被启动遍历一次最多被BFS访问一次总的时间复杂度还是 O(mn)。另一个典型变体是岛屿最大面积力扣 695。思路几乎一样唯一的区别是在BFS过程中统计访问了多少格子用一个变量记录最大值。你只需要在每次popleft()时area 1最后用max更新即可。这道题建议亲手写一遍它能帮你验证对模板的掌握程度——会做连通块就说明你能在BFS里处理计数这种最基础的附加需求。4.2 最短步数逐层扩散的直观体现网格图BFS另一大类问题是求从起点到终点的最少步数。比如经典的迷宫题#是墙.是路从S到E。你需要返回一个整数代表最少移动步数。这类题直接使用带steps的模板。因为BFS逐层扩展第一层是起点第二层是走一步能到的地方第三层是走两步能到的地方当某一层里出现了终点当前steps就是最短步数。为什么不用DFS因为DFS要枚举所有路径在最坏情况下要遍历所有可能的走法而BFS每个格子只入队一次第一次碰到终点就收工效率差别巨大。这个思路还可以扩展到状态图问题只是把网格坐标上的移动抽象成状态之间的转移。力扣 127 单词接龙就是这样每个单词是一个节点相邻单词是差一个字母的单词BFS求的是从起点单词变到终点单词的最短转换次数。理解了网格图上的BFS之后这种状态空间BFS你再做会觉得很顺因为队列、visited、步数计数的套路是一模一样的。4.3 多源BFS把起点队列一次装满多源BFS是网格题里一个很容易被人忽略的进阶点。力扣 994 腐烂的橘子就是一个典型例子初始有好几个烂橘子每一分钟烂橘子会感染上下左右相邻的新鲜橘子求多长时间能全部感染或者是否有人无法感染。我第一次做这题时一个常见的错误思路是对每个烂橘子分别做BFS取最大值。这样实现复杂而且边界情况容易漏。正确的做法是把所有初始烂橘子同时放进队列相当于它们一起开始扩散。这些源点的层级是同步增长的BFS的步数天然就是分钟数。力扣 542 01 矩阵同样用多源BFS来做所有值为 0 的格子同时入队BFS向外扩散每个格子第一次被访问时走过的层数就是它到最近 0 的距离。为什么多源BFS能得到最近距离因为你把 0 全部当作起点它们同时向四周扩散一圈相当于把所有距离为 1 的格子先标记掉再标记距离为 2 的格子。这种同时开始的语义单源BFS做不到。多源BFS在代码上的改动很小把一个起点入队改成把所有源点入队并在入队时全部标记visited。其余模板完全不变。这就是为什么我一直强调要先把标准模板理解透——题目变来变去底层操作都是那几个。4.4 从边界出发的反向BFS有些题从正面遍历会很棘手但反着来就异常简单。力扣 130 被围绕的区域就是典型给你一个二维网格里面有X和O要求把所有没和边界连通、且被X包围的O改成X。正面的做法是找出内部所有O判断是否被包围逻辑很绕。反过来想什么O不会被改能和边界连通的O不会被改。所以从边界上所有O出发做BFS把能连通的O全部标记visited这些保持原样剩下的O就是被包围的直接改成X。这一个反向的思路把题目的难度直接降了一档。这个题型教会我一个通用的做题策略当题目问哪些区域会被覆盖/感染/包围时考虑反过来从边界或源点反向扩散。BFS本身没有变变的是起始点集合的选择和扩散的方向。类似的题目还有太平洋大西洋水流问题也是从边界出发反向BFS思路如出一辙。4.5 不是所有网格图都能无脑BFS有了上面这些套路很多人会产生一种错觉网格题都可以BFS秒杀。实际上有一个边界条件BFS求最短路的前提是边权相等。如果网格里不同格子的移动代价不同比如沼泽走一步消耗 3、平地走一步消耗 1那么BFS的层数等于代价就不成立了。这种情况下需要换用 Dijkstra 算法或者用带优先队列的BFS变体。另外如果题目要求的是是否存在一条路径满足某个条件而不是最短路径DFS或回溯有时候更直接。比如网格上的排列组合类题目BFS可以做但可能要记录大量状态DFS回溯加剪枝往往写起来更自然。判断标准很简单题目问最短步数/最少时间/最低代价且移动代价一致优先BFS题目问方案数量/所有路径/是否可能优先DFS。这个选择在面试中如果能主动说出来是加分的。5. 从会写到不慌复杂度、Debug与刷题顺序5.1 复杂度为什么BFS这么稳网格图BFS的时间和空间复杂度是所有算法里最好分析的一类。每个格子最多进入队列一次每次从队列弹出时最多检查四个方向所以总操作次数是 O(mn x 4)也就是 O(mn)。visited 数组是一个 m 行 n 列的布尔矩阵空间复杂度 O(mn)。如果用了原地标记空间可以优化到 O(1) 不含输入本身。在多源BFS中由于所有源点一开始同时入队总入队次数并不会增加源点数量再多每个格子还是最多入队一次因此复杂度依然 O(mn)。这就是多源BFS比对每个源点分别做单源BFS高效的根本原因——后者是 O(k x mn)k 是源点个数网格一大就容易爆炸。面试时你被追问复杂度的概率很高所以上面这几句话很重要你是网格的行数n 是列数每个格子每个方向都要访问但每个格子最多访问一次。能说清这一点面试官会觉得你不只是背了模板而是真的理解了BFS的遍历性质。5.2 现场Debug的三条经验写网格题Debug是每个刷题人必经的苦海我自己也算是在里面泡过来的。分享三条经验都是踩过坑之后总结的。第一条打印visited矩阵而不是打印队列。队列在BFS中变化太快打印出来很难捕捉到规律打印visited则能直观地看到扩散的形状。如果visited出现了不该存在的格子问题多半出在方向数组或坐标对应上。第二条使用小网格手工推演。网格题里很多Bug不是逻辑错了而是边界写错了。一个 3x3 的网格最多9个格子完全可以用手一步步推看哪一步扩展超出了预期。先跑小样例再跑大样例能省至少十分钟的排查时间。第三条控制台里加断点检查第一次扩展的四个邻居坐标是否完全正确。很多错误其实在第一轮扩展就暴露了比如方向不对、坐标反了、把墙也入队了。如果第一轮扩展是对的后面走神的概率就低很多。5.3 适合按顺序刷的题单如果你想系统性地练网格图BFS我建议按这个顺序来从简单到复杂题目考察点难度力扣 200 岛屿数量连通块BFS入门中等力扣 733 图像渲染单源连通块替换简单力扣 695 岛屿的最大面积连通块计数变体中等力扣 994 腐烂的橘子多源BFS中等力扣 542 01矩阵多源BFS求距离中等力扣 130 被围绕的区域边界反向BFS中等力扣 127 单词接龙状态空间BFS困难力扣 417 太平洋大西洋水流问题多源反向BFS中等这个顺序的思路是先掌握最基本的连通块与单源遍历再引入多源和层级计数最后用状态空间BFS把视野打开。每道题都要做到能独立写出来而不是看一遍题解觉得哦原来是这样就翻页。网格图BFS的题目变体再多底层永远是那套四件套队列、方向、visited、层数。我觉得最后再说一个面试的小技巧当面试官让你做网格题时先说清楚这是一个网格图BFS问题因为移动代价恒为1所以BFS可以保证最短路径然后说我需要一个队列和visited数组visited在入队时标记再动手写代码。这两句话价值很高它向面试官传递的信息是你的大脑里有一套清晰的图论模型而不是在凭记忆默写模板。这个习惯我后来保持到了所有算法题上受益很明显。