30 秒识别Q1 · 733 Flood Fill：从某个像素出发，把所有与它四连通且同色的像素改成新颜色。你的第一反应是哪个模式？
看答案
图的 DFS/BFS（模板 A）。这就是洪水填充的原型，200 数岛屿是它的计数版。注意新旧颜色相同时要提前返回，否则死循环。
visited 决定你会不会死循环，用队列还是栈决定你先看近的还是先看深的。选 BFS 还是 DFS，只看一个问题：要不要「最少步数」。要，就必须 BFS——队列一层一层往外扩，第一次碰到目标时的层数就是最短距离；不要，两个都行，DFS 的递归写法通常更短。
visited 的标记时机是本章头号 bug 来源：入队时就标记，不是出队时。出队才标记的话，同一个格子会被多个邻居重复入队，轻则变慢，重则超时。
| 题面出现… | 想到 |
|---|---|
| 「岛屿 / 连通块 / 区域 / 省份的个数」 | 洪水填充，一次 DFS 吃掉一整块（模板 A） |
| 「最少步数 / 最短路径 / 最少几轮」（边权都是 1） | BFS，层数就是答案（模板 B） |
| 「同时从多个点开始扩散」（腐烂的橘子、着火） | 多源 BFS：所有起点一次性入队 |
| 「被包围的区域 / 流向两个大洋」 | 反向从边界出发扩散，比正向判断简单得多 |
| 「克隆图 / 深拷贝一张图」 | DFS + 哈希表映射旧节点 → 新节点 |
给的是 edges 数组而不是网格 | 先建邻接表 defaultdict(list)，再套同一套骨架 |
要枚举所有路径并在回来时还原现场，那是回溯（第 09 章）——本章的格子一旦标记就永久标记，绝不还原，这是两者最省事的分辨方法。题面出现「先修课 / 依赖 / 顺序」→ 拓扑排序（第 11 章）；只问「这两个点连不连通」且边是动态加进来的 → 并查集（第 12 章）——静态图数连通块用本章更直接。边有权重的最短路属于 Dijkstra，本书不覆盖。
■ 【骨架】 不变，闭着眼默写 ■ 【插槽】 随题变化，写题前先问自己填什么
DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
def num_islands(grid):
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
def dfs(i, j):
if not (0 <= i < m and 0 <= j < n): # 【骨架】先越界,再看内容
return
if grid[i][j] != "1": # 【插槽】什么格子该走
return
grid[i][j] = "0" # 【骨架】立刻标记已访问,否则会来回死循环
for di, dj in DIRS: # 【骨架】
dfs(i + di, j + dj) # 【骨架】
count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == "1": # 【插槽】什么算一个新的连通块
count += 1
dfs(i, j)
return countfrom collections import deque
def rotting_oranges(grid):
m, n = len(grid), len(grid[0])
q, fresh = deque(), 0
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
q.append((i, j)) # 【插槽】所有起点一次性入队 —— 多源的全部秘密
elif grid[i][j] == 1:
fresh += 1 # 【插槽】终止条件要盯的量
steps = 0
while q and fresh: # 【骨架】
for _ in range(len(q)): # 【骨架】先固定这一层,层数就是步数
i, j = q.popleft() # 【骨架】
for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
x, y = i + di, j + dj
if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
grid[x][y] = 2 # 【骨架】入队时就标记,不能等出队再标
fresh -= 1
q.append((x, y)) # 【骨架】
steps += 1 # 【插槽】答案:层数 / 每个点的距离
return -1 if fresh else stepsfor _ in range(len(q)) 固定住这一层——层数就是步数。'1' 改成 '0' 当作 visited；面试官说不许改输入时，换成一个 visited 集合即可。old → new 哈希映射。映射必须在递归之前写入，否则环会让你无限递归——这是它和普通 DFS 唯一的区别。1 + sum(四个方向的 dfs) 这一行把递归的合并写法演示得很干净。fresh 计数判断最后有没有剩下够不到的。* 通配建桶来找邻居」这个优化即可。grid[i][j] != '1' and 0 <= i < m 会先崩在越界索引上。顺序永远是：先边界，后内容。for _ in range(len(q))，和第 07 章层序是同一条。只要距离不要步数时，可以改成把 (点, 距离) 一起入队。'1' 网格，递归深度可达 10⁶。面试里提一句「必要时改成显式栈的迭代 DFS 或 BFS」是加分点。30 秒识别Q1 · 733 Flood Fill：从某个像素出发，把所有与它四连通且同色的像素改成新颜色。你的第一反应是哪个模式？
图的 DFS/BFS（模板 A）。这就是洪水填充的原型，200 数岛屿是它的计数版。注意新旧颜色相同时要提前返回，否则死循环。
30 秒识别Q2 · 1091 Shortest Path in Binary Matrix：0/1 矩阵里从左上角走到右下角（可走八个方向），求最短路径长度。你的第一反应是哪个模式？
BFS（模板 B）。「最短」+ 边权都是 1 = BFS，层数就是答案。DFS 也能遍历，但要枚举所有路径再取最小，指数级。八方向只是把 DIRS 换成 8 个。
30 秒识别Q3 · 207 Course Schedule：共 n 门课，给出若干「先修 A 才能修 B」的关系，判断能否修完所有课。你的第一反应是哪个模式？
拓扑排序，不是本章——题面里的「先修 / 依赖」是拓扑的专属暗号。它确实用 BFS 队列，但队列里放的是入度为 0 的点，不是「所有邻居」；要判的是有没有环，不是能不能走到。见第 11 章。
每章自测都会混入恰好一道非本章题，防止「读哪章选哪章」的条件反射；题面也一律取自本章未收录的题，避免凭记忆而非凭信号作答。