1. 从“模板”说起为什么我们需要网格图搜索模板在算法竞赛和日常开发中网格图Grid是一个极其常见的数据结构。无论是蓝桥杯、力扣还是各种笔试面试从经典的“岛屿数量”到“迷宫寻路”再到游戏中的地图遍历其底层逻辑都离不开对二维网格的搜索。很多朋友在初期会陷入一个误区每遇到一道新题就从头开始写搜索代码。结果不是递归边界设错就是方向数组漏写或者队列操作混乱调试半天比赛时间也耗光了。这就是“个人模板”的价值所在。它不是一个死板的、需要死记硬背的代码块而是你经过大量练习后提炼出的、符合自己思维习惯的、高度可靠且可复用的代码框架。当你在赛场上看到“N×M的矩阵”、“.表示通路#表示障碍”这类描述时脑子里应该瞬间弹出你那套经过千锤百炼的DFS深度优先搜索和BFS广度优先搜索模板剩下的工作就是根据具体问题微调状态定义和终止条件。今天我就结合自己多年刷题和打比赛的经验为你彻底拆解网格图中的DFS与BFS并分享我一直在用的、在第十二届蓝桥杯等国赛中验证过的个人实战模板。我们会超越简单的代码展示深入探讨两种搜索策略的本质区别、各自的适用场景、那些容易翻车的“坑”以及如何根据问题特征快速选择用DFS还是BFS。目标很简单让你下次遇到网格图问题时能条件反射般地写出正确、高效的代码。2. 网格图搜索的核心状态、方向与访问标记在深入模板之前我们必须统一几个核心概念这是所有网格搜索的基石。2.1 如何表示一个“状态”在网格搜索中一个“状态”通常就是当前所在的位置用一个坐标(x, y)来表示。在编程中我们通常使用两个整数r行和c列来对应数学上的(x, y)。这里有一个关键细节坐标系的选择。我强烈建议统一使用“数组下标”思维即grid[r][c]表示第r行、第c列的元素。行索引r从上到下递增列索引c从左到右递增。起点通常是(0, 0)。很多题目会输入n和m表示行数和列数那么有效的坐标范围就是0 r n且0 c m。在模板中边界检查是第一步必须时刻牢记。2.2 方向数组优雅地处理移动从一个格子向四周上下左右移动是网格搜索的基本操作。最笨的方法是写四个类似的if判断。而优雅的做法是使用方向数组。对于四方向上、下、左、右# Python示例 (dr, dc) 分别表示行和列的变化量 dirs [(-1, 0), (1, 0), (0, -1), (0, 1)] # 上 下 左 右对于八方向包括对角线dirs [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]使用时通过一个循环即可遍历所有方向for dr, dc in dirs: nr, nc r dr, c dc # 然后检查 (nr, nc) 是否合法且未访问注意方向数组的定义顺序有时会影响BFS的搜索“形状”或DFS的探索顺序但在绝大多数求最短路径或连通块的问题中顺序无关紧要。不过有些题目要求按特定顺序如字典序输出路径这时方向数组的顺序就至关重要了通常定义为[(0, 1), (1, 0), (0, -1), (-1, 0)]对应 ‘右’-‘下’-‘左’-‘上’。2.3 访问标记避免重复访问与死循环这是新手最容易出错的地方。无论是DFS还是BFS如果不记录哪些格子已经访问过就会在多个格子之间来回跳转陷入死循环对于DFS或导致队列爆炸对于BFS。最常用的方法是创建一个与原始网格grid同等大小的二维布尔数组visited。初始化所有值为False。当访问或即将访问某个格子(r, c)时将visited[r][c]设为True。在尝试向新格子(nr, nc)移动前首先检查visited[nr][nc]是否为False。另一种常见做法是“原地修改”如果题目允许修改输入网格可以直接将访问过的格子grid[r][c]修改为一个不会再次被访问的值例如将.通路改为#障碍。这种方法可以节省一点内存但会破坏原始数据需谨慎使用。3. 深度优先搜索模板递归与栈的实现DFS的核心思想是“一条路走到黑”不撞南墙不回头。它非常适合解决连通性问题如计算岛屿面积、判断两点是否连通和回溯问题如寻找所有可能路径。3.1 递归版本模板最常用递归版本的DFS写法简洁思维直观是竞赛中的首选。def dfs(grid, r, c): 递归DFS模板 # 1. 边界条件与合法性检查递归基 if not (0 r len(grid) and 0 c len(grid[0])): return # 越界返回 if grid[r][c] ! 1 or visited[r][c]: # 以‘1’代表陆地为例 return # 不是目标状态或已访问返回 # 2. 处理当前节点 visited[r][c] True # 标记已访问 # ... 这里可以执行一些操作例如计数、记录路径等 # 3. 递归探索四个方向 for dr, dc in dirs: dfs(grid, r dr, c dc)模板解析与实战要点递归函数签名通常包含网格grid和当前坐标(r, c)。visited数组可以作为全局变量或通过参数传递使用闭包或成员变量更佳避免传递开销。递归基这是模板的安全阀。必须首先判断坐标是否越界然后判断该位置是否可访问如是否为陆地‘1’且未被访问。顺序不能错必须先检查越界否则用grid[r][c]可能会引发数组越界错误。标记时机在确认当前节点有效后立即标记为已访问。这是一个非常重要的习惯可以防止在递归树的不同分支中重复访问同一个节点导致栈溢出。业务逻辑标记后执行问题相关的操作比如将当前格子计入岛屿面积、加入当前路径等。递归探索遍历方向数组对每个新坐标发起递归调用。3.2 迭代版本模板显式栈递归的本质是系统调用栈。我们也可以自己维护一个栈来实现DFS这在某些深度极大可能引起递归栈溢出的场景如Python默认递归深度约1000层下是必要的。def dfs_iterative(grid, start_r, start_c): 迭代DFS模板使用栈 stack [(start_r, start_c)] # 初始化栈 while stack: r, c stack.pop() # 栈顶弹出后进先出 # 注意在迭代法中弹出节点时才检查其有效性 if not (0 r len(grid) and 0 c len(grid[0])): continue if grid[r][c] ! 1 or visited[r][c]: continue # 处理当前节点 visited[r][c] True # 将邻居压入栈 for dr, dc in dirs: stack.append((r dr, c dc))迭代版注意事项检查时机不同在递归版中我们在进入函数时检查。在迭代版中我们从栈中弹出节点后必须立即检查其有效性。因为同一个节点可能会被不同的邻居多次压入栈中尽管标记后会跳过但压栈动作已发生。探索顺序由于栈是后进先出LIFO所以最后压入的邻居会最先被探索。这会导致探索顺序与递归版略有不同但就最终的“访问集合”而言两者是等价的都是深度优先。如果你需要完全一致的顺序可以逆序压入邻居。3.3 DFS模板的典型应用与变种计算连通块数量/面积LeetCode 200. 岛屿数量模板直接应用。遍历所有格子当遇到一个未访问的‘1’陆地就以它为起点调用一次DFS同时将计数器加一。这次DFS会标记整个连通岛屿的所有陆地。寻找一条可行路径在递归调用前后进行回溯操作。即在当前路径列表中加入当前节点递归探索后再从路径列表中移除当前节点。path.append((r, c)) # ... 递归探索 path.pop() # 回溯** Flood Fill图像渲染LeetCode 733**将DFS中的判断条件grid[r][c] ! 1改为grid[r][c] ! orig_color并将处理操作改为grid[r][c] new_color。4. 广度优先搜索模板队列与最短路径BFS的核心思想是“层层推进”它保证当第一次访问到一个节点时所用的步数就是从起点到该节点的最短路径长度在边权为1的图中。因此BFS是解决网格图最短路径问题的利器。4.1 标准队列模板from collections import deque def bfs(grid, start_r, start_c): BFS模板求最短路径步数 n, m len(grid), len(grid[0]) queue deque() # 通常将起点和初始步数一起入队 queue.append((start_r, start_c, 0)) # (行 列 步数) visited[start_r][start_c] True while queue: r, c, steps queue.popleft() # 先进先出 # 判断是否到达终点如果问题有特定终点 # if (r, c) (target_r, target_c): # return steps # 遍历邻居 for dr, dc in dirs: nr, nc r dr, c dc # 检查新坐标的合法性及是否可访问 if 0 nr n and 0 nc m and not visited[nr][nc] and grid[nr][nc] ! #: # 以‘#’为障碍 visited[nr][nc] True # 必须在入队时标记 queue.append((nr, nc, steps 1)) return -1 # 如果队列为空仍未找到终点说明不可达模板解析与核心技巧数据结构使用双端队列deque比普通列表list的pop(0)操作效率高得多O(1) vs O(n)。状态入队除了坐标经常需要将“附加信息”一起入队。最常见的就是当前步数。有时还需要入队路径、携带的钥匙状态等复杂信息这时可以定义一个类或元组。标记时机极其重要必须在节点入队时立即标记为已访问。这是BFS与DFS递归版的一个关键区别。为什么假设A和B两个不同的节点都能到达C。如果等从队列中弹出C时才标记那么C可能会被A和B先后放入队列两次。这会导致队列中存在重复节点浪费空间和时间。更严重的是在后续的扩散中C的邻居会被重复访问和入队可能导致指数级的冗余计算甚至使程序超时或内存溢出。牢记BFS的黄金法则——一入队就标记。步数更新新节点(nr, nc)的步数等于当前节点步数steps加1。这保证了队列中所有节点的步数是非递减的第一次到达终点时的步数就是最短步数。4.2 层序遍历的BFS有时我们不需要记录每个节点的具体步数但需要知道BFS每一层扩散到了哪些节点例如计算“距离起点为k的节点有哪些”。这时可以使用层序遍历的写法。def bfs_level_order(grid, start): n, m len(grid), len(grid[0]) queue deque([start]) visited[start[0]][start[1]] True level 0 # 当前层数也即距离 while queue: level_size len(queue) # 当前层的节点数 for _ in range(level_size): # 处理完这一整层 r, c queue.popleft() # 处理当前节点... for dr, dc in dirs: nr, nc r dr, c dc if 0 nr n and 0 nc m and not visited[nr][nc] and grid[nr][nc] ! #: visited[nr][nc] True queue.append((nr, nc)) level 1 # 进入下一层 return level - 1 # 或者根据需求返回这种写法清晰地分离了不同的“层”在需要按层处理结果时非常有用。4.3 BFS模板的典型应用迷宫最短路径无权图模板的直接应用。终点判断可能是在弹出节点时也可能是在生成邻居时后者可以提前返回略微高效。多源BFS问题不是从一个起点而是从多个起点同时开始搜索例如LeetCode 994. 腐烂的橘子。解决方案很简单初始化队列时将所有起点都加入队列并且步数都记为0。BFS会自然地从所有源点同时向外扩散。拓扑排序在网格图中较少见但在DAG中常用虽然严格来说不是网格图问题但其BFS思想Kahn算法非常经典通过维护入度队列来实现。5. DFS vs BFS如何选择与综合运用了解了两种模板后最关键的问题是面对一道新题我该用DFS还是BFS5.1 从问题本质出发做选择特性DFS (深度优先搜索)BFS (广度优先搜索)数据结构栈 (递归调用栈或显式栈)队列搜索顺序深度优先一条分支走到底广度优先一层一层向外空间复杂度O(h)其中h是递归树的最大深度。在网格图中最坏情况是O(mn)例如一条蛇形路径但通常好于BFS。O(w)其中w是搜索树最宽一层的节点数。在网格图中最坏情况也是O(mn)。对于最短路径问题BFS通常需要存储大量中间节点。时间复杂度两者都是 O(VE)其中V是节点数格子数E是边数约4V。在网格图中两者都是O(mn)。核心应用连通性分析、回溯求所有解、拓扑排序、检测环。最短路径边权为1、层序遍历、多源同步扩散。适用场景“是否连通”、“有多少种方式”、“所有可能的路径”“最短多少步”、“最近的距离”、“同时扩散多久能覆盖”选择策略问题问“最短”、“最少步数”、“最近距离”-优先考虑BFS。这是BFS的天然优势。问题问“是否可达”、“有多少连通区域”、“枚举所有可能情况路径、排列”-优先考虑DFS。DFS在回溯和枚举方面更直观。如果图非常深路径长但目标可能很浅BFS可能更快找到解。如果图非常宽或者需要记录大量路径DFS递归的空间开销可能更小但要注意递归深度限制。5.2 一个综合案例既有连通性又有最短路径有些问题需要两者结合。例如经典的“单词接龙”问题LeetCode 127它既需要找到最短转换序列BFS又需要在每一步枚举所有可能的变换DFS式的生成邻居。这时我们通常以BFS为主体框架在每一层对当前单词应用DFS思想去生成其所有“邻居单词”。在网格图中也可能有类似情况。比如在一个有钥匙和门的迷宫中LeetCode 864你需要找到最短路径但状态不仅包含位置(r, c)还包含当前拥有的钥匙集合。这仍然是一个BFS问题但状态空间变大了从(r,c)变为(r,c,keys)。你需要在BFS队列中处理这些复杂状态。6. 模板的优化与常见“坑点”剖析即使有了模板实际应用中还是会遇到各种问题。下面是我总结的几个关键优化点和常见陷阱。6.1 访问标记的“时空”权衡我们一直用独立的visited数组。但在某些内存限制极紧或追求极致速度的场景可以考虑原地修改如前所述将访问过的格子值改为一个不会再用到的值如把.改成#。节省了visited数组的空间。位图压缩如果状态空间很大例如10^3 x 10^3一个bool数组可能占用数MB内存。如果状态种类很少可以考虑用int数组的每一位来标记状态或者使用set、bitset等数据结构。但在竞赛中1000x1000的bool数组约1MB通常是可接受的。6.2 方向数组的“剪枝”优化方向数组定义了搜索顺序。在某些问题中我们可以根据当前状态动态调整方向数组实现剪枝。只能向右/向下移动如果题目规定如某些数字三角形或最小路径和问题那么方向数组只需包含[(1,0), (0,1)]这大大减少了搜索分支。根据当前方向决定比如“贪吃蛇”类问题蛇头当前朝向会影响下一步可走的方向。6.3 队列初始化的“多源”技巧当问题不是从单一起点而是从多个起点如多个火源、多个感染源开始时标准的BFS模板只需稍作修改queue deque() for source in all_sources: queue.append((source_r, source_c, 0)) visited[source_r][source_c] True # 然后正常进行BFS循环所有起点同时入队且步数均为0。BFS过程会自动处理多个源的扩散和冲突谁先到谁标记。6.4 易错点排查清单数组越界永远先检查nr和nc是否在[0, n)和[0, m)范围内再访问grid[nr][nc]或visited[nr][nc]。这是最常见的运行时错误。BFS忘记在入队时标记如前所述这会导致重复入队和超时。务必在queue.append()之前或紧随其后执行visited[nr][nc] True。DFS递归深度过大Python默认递归深度约1000。对于大型网格如1000x1000如果搜索路径很长递归DFS可能引发RecursionError。此时必须改用迭代DFS显式栈或BFS。起点/终点就是障碍在开始搜索前务必检查起点和终点本身是否合法不是障碍物且未出界。这是一个简单的边界条件但紧张时容易忽略。visited数组未重置如果需要在同一个网格上多次调用搜索函数例如对每个连通块记得在每次调用前重新初始化visited数组或者使用一个新的visited数组。步数计数错误在BFS中起点的步数通常是0。如果题目定义的步数是“移动次数”那么从起点到相邻格子的步数就是1。确保你的步数逻辑与题目定义一致。一个技巧是在初始化队列时起点步数设为0当探索邻居时新步数 当前步数 1。7. 从模板到实战经典题型精讲让我们用两个经典问题来串联并运用上述模板和技巧。7.1 案例一岛屿的最大面积LeetCode 695—— DFS的典型应用问题给定一个二进制网格1代表陆地0代表水域。计算网格中岛屿的最大面积。岛屿面积是相邻上下左右陆地的数量。分析这是典型的连通性问题求每个连通块的大小取最大值。显然用DFS或BFS遍历每个连通块并计数。这里用递归DFS演示因为它写起来更简洁。class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) - int: if not grid: return 0 n, m len(grid), len(grid[0]) visited [[False] * m for _ in range(n)] dirs [(-1,0),(1,0),(0,-1),(0,1)] max_area 0 def dfs(r, c): # 递归基越界、不是陆地、已访问 if not (0 r n and 0 c m): return 0 if grid[r][c] 0 or visited[r][c]: return 0 # 处理当前节点 visited[r][c] True area 1 # 当前格子贡献面积1 # 递归探索四个方向累加面积 for dr, dc in dirs: area dfs(r dr, c dc) return area for i in range(n): for j in range(m): if grid[i][j] 1 and not visited[i][j]: # 发现一个新的岛屿计算其面积 current_area dfs(i, j) max_area max(max_area, current_area) return max_area关键点主循环遍历每个格子当发现一个未访问的陆地时启动一次DFS。DFS函数返回以(r,c)为起点的岛屿面积。内部通过递归累加四个方向的面积。visited数组防止重复计数。7.2 案例二地图中的最高点LeetCode 1765—— 多源BFS的典型应用问题给你一个矩阵其中0代表水域1代表陆地。需要生成一个高度矩阵使得高度差尽可能大但相邻格子高度差至多为1且水域高度必须为0。求可行的最高点。分析这本质上是一个多源BFS问题。所有水域高度0作为起点向四周的陆地扩散。每次扩散高度增加1。这样能保证从任意水域到任意格子的“距离”高度差是满足条件的最短距离从而使得整体高度最大化。from collections import deque from typing import List class Solution: def highestPeak(self, isWater: List[List[int]]) - List[List[int]]: n, m len(isWater), len(isWater[0]) # 初始化结果矩阵-1表示未访问即陆地 height [[-1] * m for _ in range(n)] queue deque() dirs [(-1,0),(1,0),(0,-1),(0,1)] # 多源BFS初始化将所有水域入队 for i in range(n): for j in range(m): if isWater[i][j] 1: height[i][j] 0 # 水域高度为0 queue.append((i, j)) # 标准BFS过程 while queue: r, c queue.popleft() current_h height[r][c] for dr, dc in dirs: nr, nc r dr, c dc # 检查新坐标是否合法且未访问即height为-1 if 0 nr n and 0 nc m and height[nr][nc] -1: height[nr][nc] current_h 1 queue.append((nr, nc)) return height关键点初始化height矩阵水域处为0陆地处为-1表示未访问。多源起点遍历网格将所有水域坐标加入队列。BFS过程中每个新格子的高度等于其父节点高度加1。这保证了从最近水域扩散而来的距离就是该格子的高度。由于BFS的层序特性每个格子第一次被访问时设置的高度就是其满足条件的最小可能高度从而使其他方向来的路径有机会赋予它更大的高度但BFS保证了这是最短路径所以实际上就是最终高度。通过这两个案例你可以看到模板是如何被灵活套用和微调的。核心在于准确理解问题对应的“状态”、“转移”和“目标”然后将它们映射到模板的相应部分。8. 模板的边界拓展与高阶思考掌握了基础的网格DFS/BFS后我们可以思考一些更复杂的情况这也是竞赛中区分度所在。8.1 状态空间搜索不止是坐标在简单的迷宫问题中状态就是坐标(r, c)。但在很多问题中状态需要包含更多信息。例如带钥匙和门的迷宫LeetCode 864状态是(r, c, keys)其中keys是一个位掩码表示当前拥有的钥匙。最短路径交替颜色LeetCode 1129状态是(node, color)表示到达某个节点时最后一步使用的边颜色。推箱子游戏状态是(person_r, person_c, box_r, box_c)。对于这类问题BFS仍然是求最短路径的首选但队列中的元素和visited数组的维度需要相应扩展。visited可能变成一个字典dict或高维数组用于记录(r, c, state)这个复合状态是否被访问过。8.2 双向BFSBidirectional BFS当起点和终点都明确且状态空间很大时双向BFS可以显著减少搜索空间。其思想是从起点和终点同时开始BFS当两个搜索 frontier 相遇时路径长度就是两边步数之和加1如果相遇在边上或加0如果相遇在节点。实现要点维护两个队列和两个visited字典记录节点及从该方向出发的步数。每次迭代选择节点数较少的那一边进行扩展平衡搜索。当从一边扩展出的节点在另一边的visited中已经存在时说明相遇计算总路径。在网格图中如果起点和终点固定且网格很大双向BFS可以将时间复杂度从 O(b^d) 降低到 O(b^(d/2))其中b是分支因子d是路径长度。8.3 迭代加深搜索IDS与DFS的平衡迭代加深搜索Iterative Deepening DFS是一种结合了DFS空间效率和BFS最优性在边权为1时的算法。它通过限制深度进行多次DFS设置深度限制depth_limit 0。执行深度限制为depth_limit的DFS即递归深度不超过depth_limit。如果找到目标返回否则depth_limit 1回到步骤2。它的空间复杂度是 O(d)d是深度和DFS一样当路径存在时它能找到最短路径和BFS一样。虽然看起来重复搜索了很多上层节点但在分支因子较大的情况下底层节点占主导其额外开销是可接受的。在状态空间巨大、且要求最短路径但内存不足以进行完整BFS时IDS是一个备选方案。网格图上的DFS与BFS是算法领域最基础也最重要的两种搜索策略是构建更复杂算法如A*、Dijkstra的基石。我分享的这些模板和经验都是在无数次“Wrong Answer”和“Time Limit Exceeded”中总结提炼出来的。真正的掌握不在于背诵代码而在于理解其背后的思想和适用场景并能在看到新问题时迅速将其拆解、归类并套用或修改你的模板。最后一个最朴素的建议多动手实现多调试边界。尝试用DFS和BFS分别解决同一道题如“岛屿数量”感受它们的异同。然后去挑战一些更复杂的变种问题。当你不再需要刻意回忆模板而是能根据问题描述自然地在脑海中构建出搜索树时你就真正拥有了这项核心能力。