深度 & 广度优先搜索LeetCode 算法学习手册 · Python 3
从「走完一座岛」到「让所有橘子同时传播」，用一组网格问题建立可迁移的搜索思维：状态是什么，何时标记，是否撤销，答案在哪里产生。
先看路线：同一张网格，三种搜索语义
输入题单分为两组，每组 3 项。岛屿数量、岛屿的最大面积各出现 2 次，因此本手册保留全部 6 个条目，拆成 DFS 与 BFS 独立学习单元，共对应 4 道不同题目。每个单元都提供完整讲解、代码与推演，可以单独复习和标记。
| 阶段 | 内容与顺序 | 通过标准 |
|---|---|---|
| 01 基础与核心模板 | 网格建图 → visited → 栈与队列 → 路径状态 | 能说明发现时标记的原因；区分全局访问和当前路径 |
| 02 DFS 典型应用 | 200 岛屿数量 → 695 岛屿的最大面积 | 独立写出显式栈；解释返回值与连通块统计 |
| 03 BFS 与进阶传播 | 200 岛屿数量 → 695 最大面积 → 994 腐烂的橘子 | 独立写出队列遍历、多源初始化、逐层计时 |
| 04 回溯与剪枝 | 79 单词搜索 → 算法比较 → 自测 | 解释撤销状态、短路返回与剪枝的正确性 |
4 天学习计划 + 间隔复习
| 时间 | 任务 | 可检验的产出 |
|---|---|---|
| Day 1 · 60–90 分钟 | 基础章节、200 DFS、695 DFS | 画一遍搜索过程；闭卷写出显式栈和面积返回式 |
| Day 2 · 45–60 分钟 | 200 BFS、695 BFS；比较两种遍历 | 把栈改成队列；说清为什么面积不按层累计 |
| Day 3 · 45–60 分钟 | 994 两种 BFS；手算分钟数 | 通过无新鲜、无源、不可达、多源重叠四类边界 |
| Day 4 · 60–90 分钟 | 79 三种写法、剪枝与面试复述 | 构造需要撤销 visited 的反例；成功返回后网格完整恢复 |
| 第 7 / 14 / 30 天 · 各 20–40 分钟 | 随机抽取连通块、多源、路径搜索各一题 | 先口述不变量，再在限定时间内完成代码和复杂度分析 |
“已掌握”建议标准：不看答案写出代码、独立推演一个反例、准确说明最坏复杂度。6 个单元分别计进度；只有对应单元全部掌握，该题才计入 4 道不同题目的完成数。
第一阶段 · 基础知识与核心模板
1. 网格是隐式图，不需要先建邻接表
把每个可进入的格子看作一个顶点，把上下左右相邻的格子之间的关系看作一条边。坐标 (r, c) 就是节点标识；邻居通过方向数组即时计算。设网格为 m × n，顶点最多 mn 个，每个顶点最多 4 条邻接边，因此一次完整遍历为 O(V + E) = O(mn)。
四方向统一写为 ((1, 0), (-1, 0), (0, 1), (0, -1))；先确认 0 ≤ r < m 且 0 ≤ c < n，再读取网格。Python 的负数下标会访问末尾，不能用“没报错”判断边界正确。
2. 为什么必须有访问标记？
网格含有环：从 A 走到 B 后，又能从 B 回到 A。不标记会无限递归或反复入队。在发现节点、放入栈或队列时就标记，保证每个节点只被加入一次。若等出队才标记，同一格可能被多个父节点重复加入，面积也容易重复统计。
| 状态语义 | 何时记录 | 何时撤销 | 本专题应用 |
|---|---|---|---|
| 全局 visited：此格已归属某个连通块 | 进入递归 / 入栈 / 入队时 | 本次求解不撤销 | 200、695 |
| 全局传播状态：该橘子已被安排腐烂 | 发现新鲜橘子并入队时 | 不撤销 | 994 |
| 当前路径 path：该格正在拼接这个候选单词 | 匹配成功、搜索后继之前 | 离开当前调用前恢复 | 79 |
交互实验：同一张岛屿，DFS 与 BFS 怎样走？
固定从 (0, 0) 出发，方向顺序为下、上、右、左。选择算法，点击“下一步”观察待处理容器。为了突出显式栈的 LIFO 机制，DFS 按方向顺序入栈，因此最后加入的右侧邻居会先弹出；递归 DFS 按方向顺序调用时则先向下走。访问顺序不同，连通块不变。
本实验仅走完起点所在的连通块；其他岛屿要由外层扫描再次启动搜索。实验不会修改题目掌握进度。
核心模板：先定状态，再定容器
| 模式 | 状态与过程 | 答案产生位置 | 完整代码位置 |
|---|---|---|---|
| Flood fill / 连通块 | 扫描所有格子；遇未访问陆地启动搜索；永久标记相邻陆地 | 启动次数是岛屿数；一次搜索的格数是面积 | 200 DFS / 695 BFS |
| 多源层序 BFS | 所有源以距离 0 一起入队；每轮固定本层长度；新发现节点下一层处理 | 最后一层时间；若仍有新鲜节点则失败 | 994 分层与时间戳 |
| 路径回溯 | 参数包含位置和字符下标；选中 → 搜索 → 撤销；不同分支共享原始棋盘 | 匹配完最后一个字符，逐层返回 True | 79 三种完整实现 |
DFS 与 BFS 的基础差别
| 维度 | DFS | BFS |
|---|---|---|
| 容器 | 递归调用栈，或 list + append / pop | collections.deque + append / popleft |
| 推进方式 | 优先沿一个分支深入 | 优先处理离起点更近的节点 |
| 适合 | 连通性、面积、路径枚举、回溯 | 连通性、等权最短路、同时传播 |
| 本专题最坏空间 | 连通块栈 O(mn)；路径栈 O(L) | 一般网格队列保守上界 O(mn) |
| 实现注意 | 长蛇形岛屿递归很深，优先显式栈 | list.pop(0) 会移动元素，不能代替 deque.popleft() |
第二阶段 · DFS 遍历与连通块统计
先用搜索把一个连通块彻底处理完，再讨论外层要统计什么。两道题共享遍历结构，但答案更新的位置不同。
01LeetCode 200 · 中等岛屿数量DFS · 统计连通块
题意与约束
给定由字符串 "1"（陆地）、"0"（水）组成的矩形网格，返回四方向相连的陆地区域数量。对角接触不连通；网格外视为水，但边界格本身允许是陆地。原题 1 ≤ m,n ≤ 300，下面代码也兼容空网格。
解题思路：外层计数，内层清空一座岛
- 按行扫描网格；如果遇到
"0"，跳过。 - 遇到尚未处理的
"1"，说明找到一个新连通块，答案加 1。 - 从该格启动 DFS，将所有能连到的陆地改为
"0"。 - 继续外层扫描，同一座岛上的后续格子已被清空，不再触发计数。
不变量：每次外层启动 DFS 前，已处理的所有岛屿都已清空。一次 DFS 只沿陆地边行走，所以不会吞掉另一座岛；也会沿连通路径走完本岛所有格子，所以不会重复计数。
解法 A · 递归 DFS：理解进入与终止
from typing import List
import sys
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
sys.setrecursionlimit(max(sys.getrecursionlimit(), m * n + 50))
def dfs(r: int, c: int) -> None:
if not (0 <= r < m and 0 <= c < n):
return
if grid[r][c] != "1":
return
grid[r][c] = "0" # 进入时标记，阻止沿边返回
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
count = 0
for r in range(m):
for c in range(n):
if grid[r][c] == "1":
count += 1
dfs(r, c)
return count
| 关键代码 | 含义 |
|---|---|
if grid[r][c] != "1": return | 水与已访问陆地都终止；边界检查必须更早 |
grid[r][c] = "0" | 必须放在递归邻居前，消除回边循环 |
count += 1 | 放在外层发现新岛屿时，不在每个递归节点都累加 |
dfs(...) 无返回值 | 这里关心遍历副作用；岛屿数量由外层维护 |
解法 B · 显式栈 DFS：推荐提交版本
from typing import List
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
count = 0
for r in range(m):
for c in range(n):
if grid[r][c] != "1":
continue
count += 1
stack = [(r, c)]
grid[r][c] = "0" # 入栈时立即标记
while stack:
x, y = stack.pop()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if (0 <= nx < m and 0 <= ny < n
and grid[nx][ny] == "1"):
grid[nx][ny] = "0"
stack.append((nx, ny))
return count
stack.pop() 弹出最近加入的节点；每个邻居在入栈前就改为水，防止重复入栈。显式栈模拟待处理任务，不依赖 Python 递归深度。遍历顺序可以与递归不同，但两者找到的连通块完全相同。
示例推演：3 个连通块
输入 [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]，输出 3。图中 A / B / C 表示三次启动 DFS 所覆盖的格子。
| 扫描位置 | 动作 | 累计岛屿数 |
|---|---|---|
| (0,0) | 发现 A；一次 DFS 访问 (0,0)、(1,0)、(1,1)、(0,1) | 1 |
| (0,1)、(1,0)、(1,1) | 已被 A 的搜索改为水，跳过 | 1 |
| (2,2) | 发现 B；四周均为水 | 2 |
| (3,3) | 发现 C；同时清空 (3,4) | 3 |
| 扫描结束 | 没有残余陆地，返回 3 | 3 |
复杂度与解法比较
时间复杂度：两种解法均为 O(mn)。外层扫描 mn 格，每格最多处理一次、检查四个邻居；两层循环加 DFS 不等于 O((mn)²)，因为每次 DFS 的处理范围不会重叠。
空间复杂度：递归版最坏 O(mn) 调用栈；显式栈版最坏 O(mn)。两者都修改输入。递归结构直观，显式栈对深连通块更稳妥。
易错点与边界
- 这是字符串网格，必须比较
"1"，不能写成整数1。 - 不要沿八个方向搜索；对角两个 1 应输出 2。
- 不要在每次递归时都增加岛屿数；一个格子不等于一座岛。
- 全水返回 0；全陆地返回 1；单格陆地返回 1；单行、单列按连续段计数。
- 同一个输入不能直接交给第二份原地解法：第一份已把陆地清空。测试时使用
[row[:] for row in grid]。
02LeetCode 695 · 中等岛屿的最大面积DFS · 从遍历到返回值
题意与约束
给定只含整数 0 和 1 的矩形网格，四方向相连的一片 1 是一座岛，面积为该岛格子数。返回最大面积；没有陆地返回 0。原题 1 ≤ m,n ≤ 50。边界可含陆地，对角不连通。
解题思路：让一次 DFS 返回本次新访问的格子数
先定义函数：dfs(r, c) 返回从该坐标出发，本次递归新发现的陆地数量。越界或非陆地返回 0；首次进入陆地先标记，再把当前 1 格与四个方向新发现的数量相加。外层对每座岛的结果取最大值。
正确性关键：这里的四个方向不是四个互不相交的原始子岛。它们可能通过环互相连通；全局标记使后续分支只统计“尚未被前面分支发现”的格子，从而每块陆地恰好贡献 1。
解法 A · 递归汇总面积
from typing import List
import sys
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
sys.setrecursionlimit(max(sys.getrecursionlimit(), m * n + 50))
def dfs(r: int, c: int) -> int:
if not (0 <= r < m and 0 <= c < n):
return 0
if grid[r][c] == 0:
return 0
grid[r][c] = 0
return (1 + dfs(r + 1, c) + dfs(r - 1, c)
+ dfs(r, c + 1) + dfs(r, c - 1))
best = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
best = max(best, dfs(r, c))
return best
关键代码解释：返回值与标记顺序
水的返回值是 0，因为它不贡献面积；有效格的返回值含自身的 1。必须先 grid[r][c] = 0 再计算四个递归调用。best 跨所有岛屿保留最大值，DFS 的返回值只描述当前一次搜索中新计入的面积。
解法 B · 显式栈：每弹出一格，面积加一
from typing import List
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
best = 0
for r in range(m):
for c in range(n):
if grid[r][c] != 1:
continue
area = 0
stack = [(r, c)]
grid[r][c] = 0
while stack:
x, y = stack.pop()
area += 1
for dx, dy in directions:
nx, ny = x + dx, y + dy
if (0 <= nx < m and 0 <= ny < n
and grid[nx][ny] == 1):
grid[nx][ny] = 0
stack.append((nx, ny))
best = max(best, area)
return best
area = 0 在每个新岛屿开始时重置；best 只在整座岛遍历完成后更新。由于入栈即标记，出栈节点不重复，所以 area += 1 的次数正好等于岛屿面积。
示例推演：面积 3 与面积 4
教学示例输入 [[1,1,0,0,1],[0,1,0,1,1],[0,0,0,0,1]]，输出 4。
| 过程 | 当前结果 | 全局最大值 |
|---|---|---|
| 从 (0,0) 启动；新访问 (0,0)、(0,1)、(1,1) | 3 | 3 |
| 从 (0,4) 启动；新访问 (0,4)、(1,4)、(2,4)、(1,3) | 4 | 4 |
| 其他格已处理或是水，结束扫描 | — | 返回 4 |
递归版 A 岛的返回可以读成：dfs(1,1) = 1，dfs(0,1) = 1 + 1 = 2，dfs(0,0) = 1 + 2 = 3。这里恰好没有环；含环时访问标记仍保证不重算。
复杂度与解法比较
时间复杂度：均为 O(mn)，全局每个陆地格仅计入一次。
空间复杂度：递归栈和显式栈最坏均为 O(mn)。两种实现都会修改 grid；递归返回式方便理解“自底向上汇总”，显式栈方便处理大连通块。若要求输入不变，可用全局 visited 集合替代改写，仍为 O(mn) 额外空间。
易错点与边界
- 输入是整数网格，使用
1/0；不要套用 200 的字符串。 - 返回四方向面积的总和，不是
max；最大值只在不同岛屿之间比较。 - 不能把多座岛的面积累加为最终答案；每座岛必须重新计数。
- 全水返回 0；单格陆地返回 1；全陆地返回 mn；2×2 全 1 应为 4，能检查成环时是否重复计算。
- 递归汇总前标记，不能等递归结束才标记；否则环会反复进入。
第三阶段 · BFS 队列与多源传播
先用队列解决相同的连通块问题，再让队列中的层次代表真实时间。BFS 的价值来自“按距离从近到远”这一顺序。
03LeetCode 200 · 中等岛屿数量BFS · 发现即入队
题意与约束
网格元素为字符串 "1" 与 "0"，相邻只含上下左右，求岛屿数量。网格外是水，但边界允许陆地；原题 1 ≤ m,n ≤ 300。本单元完整使用 BFS 求解，并提供输入不变的版本。
解题思路：每次 BFS 走完一座岛
- 按行扫描；遇到尚未处理的陆地，岛屿数量加 1。
- 将起点放入
deque，同时标记为已访问。 - 不断从队首弹出坐标；将四周未访问的陆地标记并加入队尾。
- 队列为空时，这一岛屿已完全处理，再继续扫描。
队列不变量：容器里只包含已经被发现但尚未展开邻居的陆地，每个格子最多出现一次。沿路径长度归纳，任何与起点相连的陆地都会被逐层发现；水隔开的格子不会进入本次队列。
解法 A · 原地标记 BFS
from typing import List
from collections import deque
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
count = 0
for r in range(m):
for c in range(n):
if grid[r][c] != "1":
continue
count += 1
queue = deque([(r, c)])
grid[r][c] = "0"
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if (0 <= nx < m and 0 <= ny < n
and grid[nx][ny] == "1"):
grid[nx][ny] = "0" # 发现时标记
queue.append((nx, ny))
return count
| 关键代码 | 为什么这样写 |
|---|---|
deque([(r, c)]) | 每座岛单独创建队列，不把多个岛混成一次启动 |
queue.popleft() | 先进先出；deque 队首弹出为 O(1) |
grid[nx][ny] = "0" 后 append | 两个父节点同时发现该格时，只有第一个能入队 |
不使用 range(len(queue)) | 这里只求连通性，不需要按层统计 |
解法 B · 保留输入：独立 visited 集合
from typing import List
from collections import deque
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
visited = set()
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
count = 0
for r in range(m):
for c in range(n):
if grid[r][c] != "1" or (r, c) in visited:
continue
count += 1
queue = deque([(r, c)])
visited.add((r, c))
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if (0 <= nx < m and 0 <= ny < n
and grid[nx][ny] == "1"
and (nx, ny) not in visited):
visited.add((nx, ny))
queue.append((nx, ny))
return count
visited 放在外层循环之外，记录整个求解过程中发现过的陆地。每个新起点也必须先检查是否已访问；否则同一个岛会被再次计数。集合添加与队列入队同步，网格本身始终不变。
示例推演：观察发现与出队的区别
教学示例 grid = [["1","1","0"],["1","1","0"],["0","0","1"]]，输出 2。使用下、上、右、左的方向顺序，队列左侧为队首。
| 事件 | 队列（事件后） | 说明 |
|---|---|---|
| 起点 (0,0) 入队 | [(0,0)] | 标记起点，count = 1 |
| 弹出 (0,0) | [(1,0), (0,1)] | 发现下、右两个陆地 |
| 弹出 (1,0) | [(0,1), (1,1)] | 发现 (1,1) 并立即标记 |
| 弹出 (0,1) | [(1,1)] | (1,1) 已发现，不重复加入 |
| 弹出 (1,1) | [] | 第一座岛遍历完成，共 4 格 |
| 扫描到 (2,2) | [(2,2)] → [] | 新岛孤立，count = 2；返回 2 |
复杂度与优劣比较
时间复杂度：两版均为 O(mn)，集合操作按平均 O(1) 计。空间复杂度：原地版队列最坏 O(mn)；保留输入版 visited 与队列合计最坏 O(mn)。不能把任意形状网格上的队列空间一概写成 O(min(m,n))。
原地版省去 visited 的额外对象开销；保留输入版便于复用网格。与 DFS 相比，两者时间同阶；BFS 不受递归深度影响，也为后续按层传播提供基础。
易错点与边界
- 不要用
list.pop(0)；反复移动列表元素会破坏线性时间保证。 - 起点和邻居都在入队时标记，不等出队。
- visited 不应在每次 BFS 开始时清空，否则外层会再次统计旧岛。
- 全水返回 0；单格 1 返回 1；对角双陆地返回 2；2×2 全 1 返回 1，且每格只能入队一次。
- 若改用复制网格保留输入，浅拷贝外层列表不够；必须复制每一行，并计入 O(mn) 空间。
04LeetCode 695 · 中等岛屿的最大面积BFS · 统计节点数量
题意与约束
给定整数 0 / 1 网格，四方向相连的 1 构成岛屿，返回所有岛屿中最大的格子数量；全水返回 0。原题 1 ≤ m,n ≤ 50，允许边界陆地。
解题思路：队列出队次数就是面积
外层扫描找到未访问陆地，启动一次 BFS。每个格子入队即标记，因此每次出队都对应一个新的陆地格。让局部变量 area 在出队时加一，队列为空后用它更新 best。
正确性：BFS 会访问起点所在连通块的全部格子，且不跨水、不重复访问；因此该次出队总数恰好是岛屿面积。扫描所有起点后取最大值，就覆盖所有岛屿。
完整 Python 3 代码
from typing import List
from collections import deque
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
best = 0
for r in range(m):
for c in range(n):
if grid[r][c] != 1:
continue
queue = deque([(r, c)])
grid[r][c] = 0
area = 0
while queue:
x, y = queue.popleft()
area += 1
for dx, dy in directions:
nx, ny = x + dx, y + dy
if (0 <= nx < m and 0 <= ny < n
and grid[nx][ny] == 1):
grid[nx][ny] = 0
queue.append((nx, ny))
best = max(best, area)
return best
关键代码解释
area = 0属于一座岛；必须放在该岛 BFS 开始处。area += 1放在出队处。若选择入队处计数，也必须包含起点并保持每格只计一次，不能两处都加。best = max(best, area)在 BFS 完成后执行，此时 area 才是完整岛屿面积。- 这里的 BFS 不需要按层循环：面积统计格子总量，不是最远距离。
示例推演：最大层宽并不是岛屿面积
教学示例 [[1,1,0],[1,0,0],[0,0,1]]，输出 3。第一岛屿从 (0,0) 出发，距离 0 的层有 1 格，距离 1 的层有 2 格，面积是 1 + 2 = 3，不是 2。
| 出队位置 | 发现的邻居 | 当前 area | best 更新 |
|---|---|---|---|
| (0,0) | (1,0)、(0,1) | 1 | 尚未完成本岛 |
| (1,0) | 无 | 2 | 尚未完成本岛 |
| (0,1) | 无 | 3 | 队列空，best = 3 |
| 第二岛 (2,2) | 无 | 重新从 0 计到 1 | max(3,1) = 3 |
复杂度与解法比较
时间复杂度：O(mn)，四个方向的常数因子不影响阶数。空间复杂度：队列最坏 O(mn)，不额外开 visited。
DFS 递归版用返回值汇总，DFS 显式栈版和 BFS 版用局部计数器；三者都遍历整个连通块，结果一致。BFS 在这里无需利用距离性质，优势主要是实现稳定、便于迁移到多源搜索。若输入必须保留，可增加全局 visited，最坏空间仍是 O(mn)。
易错点与边界
- 把整数
1改为整数0，不要混入字符串。 - 不能把
len(queue)当作面积；它只是某个时刻尚未处理的格子数。 - 每座岛重置 area，但不能重置 best；最后返回 best，不是最后一座岛的面积。
- 全水 0；单格 1；2×2 全 1 面积为 4；不相连的两个单格岛最大面积仍为 1。
- 若出队时才标记，成环网格会重复入队并重复计面积。
05LeetCode 994 · 中等腐烂的橘子进阶 BFS · 多源最短传播
题意与约束
网格中整数 0 为空格，1 为新鲜橘子，2 为腐烂橘子。每过一分钟，已腐烂橘子四周的新鲜橘子同时腐烂。求全部橘子腐烂需要的最少分钟数；有橘子永远无法腐烂则返回 -1；一开始没有新鲜橘子返回 0。原题 1 ≤ m,n ≤ 10。
解题思路：所有源从 0 分钟同时出发
把橘子看作图节点，空格是不可穿过的障碍；每条邻接边传播耗时 1。一个新鲜橘子的最早腐烂时刻，是它到所有初始腐烂源的最短可达距离的最小值。所有橘子都腐烂的时刻，是这些最早时刻的最大值。
先扫描网格，把所有 2 一起加入队列，并统计新鲜数 fresh。每次只处理当前层已有的节点，将新腐烂节点加入下一层，整层结束才增加一分钟。某格第一次被 BFS 发现时已是最短时间；即时改为 2 可防止多个源对同一格重复计数。
解法 A · 按层计时：推荐版本
from typing import List
from collections import deque
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
while queue and fresh > 0:
for _ in range(len(queue)): # 固定本分钟开始时的队列长度
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (0 <= nr < m and 0 <= nc < n
and grid[nr][nc] == 1):
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
minutes += 1
return minutes if fresh == 0 else -1
| 关键代码 | 不变量与作用 |
|---|---|
| 初始化将所有 2 入队 | 所有源拥有同一时间 0；不是逐个源跑完整个 BFS |
while queue and fresh > 0 | 无新鲜时立即结束，初始无新鲜返回 0 |
for _ in range(len(queue)) | range 开始前求值一次，固定本层长度；新入队节点不能在本分钟继续传播 |
改为 2、fresh -= 1、入队 | 发现一次只扣一次，避免重复污染 |
整层末尾 minutes += 1 | 一轮表示从当前时刻推进到下一分钟 |
fresh == 0 才返回 minutes | 队列空不一定成功：孤立新鲜橘子仍可能存在 |
解法 B · 节点携带时间戳
from typing import List
from collections import deque
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 2:
queue.append((r, c, 0))
elif grid[r][c] == 1:
fresh += 1
answer = 0
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
while queue:
r, c, time = queue.popleft()
answer = max(answer, time)
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (0 <= nr < m and 0 <= nc < n
and grid[nr][nc] == 1):
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc, time + 1))
return answer if fresh == 0 else -1
队列存储 (r, c, time)，初始源 time 为 0，新邻居为 time + 1。不用手动划分层，最终取最大出队时间。队列按非递减时间出队；同一个新鲜节点只被最早到达的波前加入一次。即使初始只有腐烂橘子，answer 仍为 0。
示例推演：为什么答案是 4 分钟？
输入 [[2,1,1],[1,1,0],[0,1,1]]，输出 4。图中文字表示该位置最早腐烂的时刻，× 表示空格。
| 时刻 | 本时刻新腐烂坐标 | 剩余 fresh |
|---|---|---|
| 0 | 初始源 (0,0) | 6 |
| 1 | (1,0)、(0,1) | 4 |
| 2 | (1,1)、(0,2) | 2 |
| 3 | (2,1) | 1 |
| 4 | (2,2) | 0 → 返回 4 |
复杂度与解法比较
时间复杂度：两版均 O(mn)，先扫描、后扩散，每个橘子最多入队一次。空间复杂度：两版队列最坏 O(mn)；所有格子都初始腐烂时，初始化就可能入队 mn 个。
分层版每个元素仅存坐标，时间变量集中维护；时间戳版更容易推演各节点到达时刻，队列元素多一个字段。两者都会修改输入。普通单源 DFS 的第一次到达不保证最短时间；为此题反复松弛距离会增加实现和分析负担。
易错点与边界
- 所有初始腐烂橘子要一起入队；传播可以来自任意源。
grid = [[0,2]]→ 0；全空格 → 0；[[1]]→ -1；[[2,1]]→ 1。[[2,1,1],[0,1,1],[1,0,1]]→ -1，左下角不可达。- 只有 1 格新鲜且没有源时，while 不会启动，但 fresh > 0，必须返回 -1。
- 每个节点入队就改为 2；否则多源交汇处 fresh 会被多扣。
- 不能仅依据曼哈顿距离估时：空格障碍会迫使绕路，甚至让目标不可达。
第四阶段 · 路径回溯与安全剪枝
连通块只问能否到达某格；单词搜索还要记录以什么路径到达。状态改变之后，访问标记的生命周期也必须改变。
06LeetCode 79 · 中等单词搜索进阶 DFS · 回溯与剪枝
题意与约束
在字符矩阵 board 中寻找单词 word：从任意格开始，按字符顺序沿上下左右相邻格移动；一次单词路径中不能重复使用同一个格子。存在合法路径返回 True，否则返回 False。字母区分大小写。原题 1 ≤ m,n ≤ 6，1 ≤ L = len(word) ≤ 15，只含大小写英文字母。
解题思路：坐标、字符位置、当前路径缺一不可
定义 dfs(r, c, k)：在当前已经占用的路径约束下，能否从 (r,c) 开始匹配 word[k:]。前缀 word[:k] 已匹配且对应格子不可复用。实际状态还包含当前路径占用集合，这个集合用棋盘临时标记或 path 集合隐式传递。
- 越界、格子已被当前路径使用、字符不等于 word[k]，返回 False。
- 若字符匹配且 k 是最后一个下标，返回 True。
- 临时占用当前格，对四个邻居搜索 k + 1；任意方向成功即可。
- 离开当前函数前撤销占用，再把搜索结果返回给父调用。
- 枚举每个格子为起点，直到找到一条完整路径或全部失败。
不变量：每次进入 dfs 时，临时标记的格子恰好对应已匹配的前缀；每次调用返回后，调用前的棋盘状态被完全恢复。由此其他分支可重新使用这些格子。
解法 A · 原地占位，成功与失败都恢复
from typing import List
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if not word:
return True
if not board or not board[0]:
return False
m, n = len(board), len(board[0])
if len(word) > m * n:
return False
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
def dfs(r: int, c: int, k: int) -> bool:
if not (0 <= r < m and 0 <= c < n):
return False
if board[r][c] != word[k]:
return False
if k == len(word) - 1:
return True
char = board[r][c]
board[r][c] = "#" # 仅对当前路径禁用
found = False
for dr, dc in directions:
if dfs(r + dr, c + dc, k + 1):
found = True
break
board[r][c] = char # 成功与失败都恢复
return found
for r in range(m):
for c in range(n):
if dfs(r, c, 0):
return True
return False
| 关键代码 | 作用 |
|---|---|
k == len(word) - 1 | 当前字符已匹配，故完成整个单词；最后一格无需再占位 |
board[r][c] = "#" | 题目字符只含英文字母，# 不会与正常字符相等 |
找到后仅设置 found = True 并 break | 延迟返回，保证本层仍执行恢复语句 |
board[r][c] = char | 回到其他方向或起点前恢复，无论是否找到答案 |
len(word) > m * n | 一格不能重复用，长度过大必不可能 |
解法 B · path 集合：不改动棋盘
from typing import List
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if not word:
return True
if not board or not board[0]:
return False
m, n = len(board), len(board[0])
if len(word) > m * n:
return False
path = set()
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
def dfs(r: int, c: int, k: int) -> bool:
if not (0 <= r < m and 0 <= c < n):
return False
if (r, c) in path or board[r][c] != word[k]:
return False
if k == len(word) - 1:
return True
path.add((r, c))
found = any(dfs(r + dr, c + dc, k + 1)
for dr, dc in directions)
path.remove((r, c))
return found
return any(dfs(r, c, 0) for r in range(m) for c in range(n))
path 只记录当前递归链上的坐标，不是整个求解过程的全局 visited。每次 add 后都与 remove 配对，兄弟分支和其他起点可以重新使用该格。any 遇 True 会短路，但短路只是结束子调用枚举，之后的 path.remove 仍会执行。
解法 C · 长度、频次与稀少端点剪枝
from typing import List
from collections import Counter
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if not word:
return True
if not board or not board[0]:
return False
m, n = len(board), len(board[0])
if len(word) > m * n:
return False
available = Counter(ch for row in board for ch in row)
required = Counter(word)
if any(available[ch] < need for ch, need in required.items()):
return False
# 无向邻接中路径可以反转，从更稀少的端点出发
if available[word[0]] > available[word[-1]]:
word = word[::-1]
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
def dfs(r: int, c: int, k: int) -> bool:
if not (0 <= r < m and 0 <= c < n):
return False
if board[r][c] != word[k]:
return False
if k == len(word) - 1:
return True
char = board[r][c]
board[r][c] = "#"
found = any(dfs(r + dr, c + dc, k + 1)
for dr, dc in directions)
board[r][c] = char
return found
return any(dfs(r, c, 0) for r in range(m) for c in range(n))
三种剪枝分别有清晰的必要条件或等价变换：
- 长度检查：L > mn 时格子不够，直接返回 False。
- 频次检查：word 所需某个字母数大于棋盘可用数，必定无解。但频次足够仅代表“数量够”，不能保证位置相连。
- 反转单词：网格四方向邻接是无向关系；存在 word 路径当且仅当存在 reversed(word) 路径。若末字符在棋盘中更少，就从末端搜起，通常减少候选起点；最坏复杂度不变。
例如棋盘有很多 A、只有一个 B，寻找以 A 开头、B 结尾的词，从 B 反向找通常更快。不要把“频次足够”直接当作 True，也不要对有向移动规则未经证明地使用反转。
示例推演：ABCCED 的一条成功路径
输入 board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]，word = "ABCCED"，输出 True。高亮路径只描述成功分支，实际 DFS 还会先尝试一些不匹配的方向。
| 字符下标 k | 当前格 | 动作与返回 |
|---|---|---|
| 0 / A | (0,0) | 匹配，临时占用 A，继续找 B |
| 1 / B | (0,1) | 匹配，占用 B，继续找 C |
| 2 / C | (0,2) | 匹配，占用 C，继续找下一个 C |
| 3 / C | (1,2) | 匹配，向下找到 E |
| 4 / E | (2,2) | 匹配，向左找到 D |
| 5 / D | (2,1) | 最后字符匹配，返回 True；调用链逐层恢复占用 |
同一棋盘 word = "SEE" → True，可走 (1,3) → (2,3) → (2,2)；word = "ABCB" → False，A → B → C 后所需的 B 只能回到已经使用的 (0,1)，不合法。
为什么必须回溯：一个可亲手推演的反例
教学例：board = [["A","A"],["A","B"]]，word = "AAA"，正确答案是 True，但把 visited 永久保留的写法会错误返回 False。
- 先从 (0,0) 的 A 出发，向下走 (1,0) 的 A；它没有可用的第三个 A，分支失败。
- 回到 (0,0)，尝试向右走 (0,1) 的 A；它同样找不到第三个 A，这个起点整体失败。
- 如果不撤销标记，此时三个 A 都已经永久占用；后面的起点会被直接跳过，错误返回 False。
- 正确回溯会恢复三个格子。从下一个起点 (0,1) 出发，走 (0,1) → (0,0) → (1,0)，恰好得到 AAA。
再看兄弟分支换路：board = [["A","B","C"],["B","X","D"]]，word = "ABCD"。从 A 向下走 B(1,0) 后找不到 C，撤销该分支；再向右走 B(0,1) → C(0,2) → D(1,2) 即成功。
访问标记描述的是当前路径占用了什么，不能把失败分支的占用带入后续搜索。也不能仅缓存 (r,c,k) 的失败结果，因为同一位置、同一字符下标，在不同已用路径下拥有不同的可用后继。
复杂度：指数来自路径分支，而非网格扫描
设 L = len(word)，代码会先检查 L ≤ mn。每个起点第一步最多 4 个选择，之后刚走来的父格已禁用，通常最多 3 个方向继续扩展；边界和字符不匹配会进一步减枝。
时间复杂度：常用紧一些的上界写作 O(mn · 3ᴸ)（第一层的 4 作为常数处理）；更宽松且易推导的 O(mn · 4ᴸ) 也是合法上界。三版最坏均仍为指数级。频次版额外扫描 O(mn + L)，不改变总体最坏上界。
空间复杂度：基础原地版为 O(L) 递归栈；path 版集合最多含 L 个格子，加递归栈合计 O(L)；剪枝版 O(L + Σ)，Σ 为字符种类数，题目只含大小写字母，Σ ≤ 52，可视作 O(L)。反转单词需要 O(L) 临时字符串。所有版本返回后 board 恢复为原始内容。
| 解法 | 优势 | 代价 / 使用场景 |
|---|---|---|
| 原地占位 | 代码短；无需额外坐标集合 | 中途修改棋盘，必须保证所有返回路径恢复 |
| path 集合 | 不写入棋盘；状态语义直观 | 哈希集合操作有常数开销；add/remove 必须配对 |
| 频次 + 反向剪枝 | 无解数量不足时立即终止；减少候选起点 | 额外一次计数；不改善指数级最坏界 |
易错点与边界
- 先比较当前字符，再判断是否到达最后一个字符，不能仅因为 k 到末尾就成功。
- 不能用一个永久 visited 阻止所有路径使用同格；只能禁止当前路径重复。
- 不要在子调用成功后立即
return True跳过恢复语句。 - 单格
[["A"]]查 A 为 True，查 B / AA 为 False；L > mn 必为 False。 - 棋盘
[["A","B"],["C","D"]]查 AD 为 False：对角不算相邻。 - 代码额外约定空单词返回 True，空棋盘查非空词返回 False；原题约束不会给空输入。
- 不要复制整个棋盘到每个递归分支，也不要每层切片 word；用 k 传递位置可减少额外开销。
算法对照：用问题目标选择搜索方式
| 问题 | 答案更新 | visited 生命周期 | 推荐方案 | 最坏时间 / 空间 |
|---|---|---|---|---|
| 200 岛屿数量 | 新启动一次搜索，答案加 1 | 整个求解期间永久有效 | 显式栈 DFS 或 BFS | O(mn) / O(mn) |
| 695 最大面积 | 一座岛的格数取最大 | 整个求解期间永久有效 | DFS 汇总或 BFS 计数 | O(mn) / O(mn) |
| 994 腐烂的橘子 | 所有新鲜节点最早到达时间取最大 | 发现即腐烂，不撤销 | 多源 BFS | O(mn) / O(mn) |
| 79 单词搜索 | 有一条路径完整匹配即成功 | 仅当前候选路径有效 | DFS 回溯 + 剪枝 | O(mn·3ᴸ) / O(L)（固定字符集） |
面试时，用四句话解释你的代码
- 状态：200 / 695 的节点是坐标；994 多一个最早到达时间；79 还有单词下标与当前路径占用。
- 推进：连通块可用栈或队列；每步耗时相同且求最早到达时，BFS 按距离非递减展开。
- 不重复：全局访问在发现时标记；当前路径标记在本层返回前撤销。
- 答案：启动次数、单次访问数、最后传播时间、是否存在完整匹配，分别决定答案在何处产生。
三条不能混用的“模板句”
| 模板句 | 成立原因 | 不能误用到哪里 |
|---|---|---|
| 连通块发现即标记，后续不撤销 | 同一节点被不同路径到达，对连通性没有区别 | 79 中路径已用格子改变了后续可选集合 |
| BFS 首次发现就是最短距离 | 边的代价一致，队列按层推进 | DFS 首次发现；任意正权边的普通 FIFO BFS |
| 回溯返回前恢复现场 | 兄弟分支应从同一状态开始尝试 | 200 / 695 撤销全局标记会反复统计和成环 |
边界自测与复盘清单
先猜输出并解释原因，再展开答案。这些自测不执行 Python；所有完整解法均另有自动校验。
200：[["1","0"],["0","1"]] 有几座岛？
2。两格只对角接触，四方向不连通。
695：[[1,1],[1,1]] 的最大面积是多少？
4。网格有环，每个格子只能计一次。
994：[[2,1,1,1,2]] 需要几分钟？
2。两端的源同时扩散，中间在第 2 分钟腐烂。
994：[[1,0,2]] 返回什么？
-1。新鲜橘子被空格隔开，无法到达。
79：[["A","B"]] 查找 ABA 可以吗？
False。长度已超过格子总数，且不能回到 A 重复使用。
79：为什么缓存 (r,c,k) 的失败结果可能错误？
这个键没有包括当前路径已用格子。同位置同字符下标，剩余可用邻居可能不同，不能直接合并状态。
为什么外层双循环 + 每次搜索不是平方复杂度？
200 / 695 每格最多被某一次搜索发现一次；将所有搜索的访问次数相加仍为 O(mn)。79 撤销状态，会在不同路径重复访问，不能用这个论证。
闭卷能力检查（与题目进度独立保存）
最终复习顺序
闭卷写 200 显式栈，随后改成 BFS；从返回岛屿数改成最大面积；把单源改成所有腐烂源一起入队并按层计时；最后重新定义路径状态，写出 79 的占用与恢复。每次改动都说清楚：改了什么状态、为什么正确、最坏会占多少空间。
主题、6 个单元掌握状态、能力自测保存在当前浏览器的 localStorage 中。更换浏览器或清除网站数据不会同步；部分隐私设置可能禁止 file:// 存储，届时页面会提示“仅本次有效”，阅读与交互仍可继续。打印会移除导航和按钮、展开自测答案，并将代码自动换行。