误区一：把所有同色格子都改掉
Flood Fill 只改起点所在的同色连通块。右下角的 1 虽然同色，但和起点之间被 0 隔开，所以不能改。
LC733
图像渲染 · 普通人也能看懂版
Flood Fill / 网格 DFS：像画图软件油漆桶一样，只填起点所在的同色连通块。
先理解题目在问什么，再把二维网格翻译成图。动画只服务于四件事：起点、原颜色、四方向、停止边界。
画图软件油漆桶网格图建模时间 O(m*n)空间 O(m*n)
from problem
题目在问什么
把这题想成画图软件油漆桶：你在一张像素图上点一下，软件会把点到的那一片相同颜色区域换成新颜色。
注意：不是所有同色格子都会被改。只有“和起点原颜色相同，并且能从起点通过上下左右走到”的格子才会被改。
image
image 是二维图片网格，每个数字代表一个颜色。
sr、sc
sr、sc 是点击位置：第 sr 行、第 sc 列。
newColor
newColor 是要填充的新颜色，也就是油漆桶倒下去的颜色。
范围
只填充和起点原颜色相同，并且四方向连通的区域。
油漆桶规则
1
1
1
1
1点击
0
1
0
1
右下角的 1 虽然颜色一样，但被 0 隔开，不能从起点四方向走到，所以最后仍然是 1。
to graph
为什么这是图问题
| 每个格子 | 每个格子 = 一个节点 |
|---|---|
| 相邻关系 | 上下左右相邻 = 边 |
| 斜方向 | 斜方向不算连通 |
| 搜索目标 | DFS/BFS 找到起点所在的同色连通分量 |
网格 DFS 不是在“找所有数字 1”，而是在图上从起点出发，沿着边走，只收集值等于 oldColor 的节点。
四方向：上、下、左、右都算边。
斜方向：看起来挨着，但没有边。
core variables
核心变量
oldColor := image[sr][sc]
oldColor 是起点原颜色。本例点击 (1,1)，所以 oldColor=1。
image[r][c] == oldColor
后续每个格子是否能被填充，都要判断 image[r][c] == oldColor。
不要用 newColor 判断能否继续扩散
newColor 是填上去的新颜色，不是“原本属于这片区域”的证据。
edge case
边界条件警告
if oldColor == color { return image }
如果目标颜色和原颜色相同，图片本来就是目标结果，不需要 DFS。
更重要的是：改色本身起到了 visited 标记作用。若 oldColor == newColor，改完后格子仍然满足 oldColor，可能重复访问，甚至导致递归问题。
storyboard
8 步动画分镜
从输入网格开始，逐帧看 oldColor、四方向检查、递归扩散、停止边界和最终结果。
边界测试 · 切换后整段动画会重算
帧 1/8Scene 1
当前步骤
Step 1：先看输入图片
image 是二维图片网格，每个数字可以理解成一个颜色编号。现在点击位置是 sr=1、sc=1，目标 newColor=2。
image=[[1,1,1],[1,1,0],[1,0,1]] · sr=1 · sc=1 · color=2
观察顺序提示
- 1. 先看当前坐标有没有越界。
- 2. 再看当前值是不是 oldColor。
- 3. 能填就改成 newColor，再查上下左右。
当前帧重点
先把二维数组看成一张 3×3 的像素图。
像素网格 · 油漆扩散
Step 1：展示输入网格 [[1,1,1],[1,1,0],[1,0,1]]10,0
10,1
10,2
11,0
11,1start
01,2
12,0
02,1
12,2
等待四方向检查
动作：先把二维数组看成一张 3×3 的像素图。
不变量：还没有填色，所有格子保持输入值。
代码 · 当前高亮行随帧切换
1func floodFill(image [][]int, sr int, sc int, color int) [][]int {2 oldColor := image[sr][sc]3 if oldColor == color {4 return image5 }6 m, n := len(image), len(image[0])7 var dfs func(r, c int)8 dfs = func(r, c int) {9 if r < 0 || r >= m || c < 0 || c >= n {10 return11 }12 if image[r][c] != oldColor {13 return14 }15 image[r][c] = color16 dfs(r-1, c)17 dfs(r+1, c)18 dfs(r, c-1)19 dfs(r, c+1)20 }21 dfs(sr, sc)22 return image23}
代码对应流程
oldColor := image[sr][sc]：先保存起点原颜色。
image[r][c] != oldColor：所有扩散资格都和 oldColor 比较。
当前高亮：无
不变量 · 算法为什么对
- · oldColor 是起点原颜色，后续扩散只比较 oldColor。
- · DFS 只访问不越界且 image[r][c] == oldColor 的格子。
- · 斜方向没有边，不属于四方向连通。
- · 不使用额外 visited 数组，因为改色本身起到了 visited 标记作用。
时间线 · 点击跳转
complexity
复杂度
时间复杂度：O(m*n)
m 是行数，n 是列数。每个格子最多被 DFS 处理一次，所以总时间是 O(m*n)。
空间复杂度：O(m*n)
递归调用栈在最坏情况下可能包含整个同色连通块，也就是 O(m*n)。不使用额外 visited 数组，因为改色本身起到了 visited 标记作用。
common mistakes
常见误区
把所有同色格子都改掉；把斜方向也算连通；忘记 oldColor == newColor；改色后还用当前颜色判断；复杂度写成 O(1) 空间
误区二：把斜方向也算连通
这题只看上下左右四方向。斜着碰到不算边，也不算连通。
误区三：忘记 oldColor == newColor
如果目标颜色和原颜色一样，改色不会产生 visited 标记，DFS 可能在同一片区域反复访问。
误区四：改色后还用当前颜色判断，导致逻辑混乱
能不能继续扩散要比较 oldColor，不要用 newColor 判断。newColor 是填上去的颜色，不是扩散资格。
误区五：复杂度写成 O(1) 空间但忽略递归栈
即使没有额外 visited 数组，递归 DFS 的调用栈最坏也可能达到 O(m*n)。
interview answer
我会先记录 oldColor := image[sr][sc]，它是起点原颜色。若 oldColor == color，直接返回，避免重复递归。否则从起点 DFS，只访问不越界且 image[r][c] == oldColor 的格子，先把它改成 color，再向上下左右四个方向递归。斜方向不算连通，右下角即使也是 1，只要不和起点四方向连通就不会被改。
LC200 岛屿数量 — 同样是四方向 floodLC695 岛屿最大面积 — DFS 返回连通块大小LC130 被围绕的区域 — 从边界反向 flood