题目重点：根据题目明确的三次实现追问，比较同一连通分量的正确性、栈空间和颜色不变边界。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版为非空矩形整数色图、四邻接，从合法 (sr,sc) 出发，只将与起点旧颜色连通的格子改为 new_color，返回新图而不修改输入。
- 题目只暗示标准题名，不能断言实际语言、原地修改要求或颜色范围；代码把三种 method 放在一个可对照接口中。
解题路线
- 先保存起点旧色；若旧色等于新色，直接返回拷贝，否则会反复把已访问格识别为旧色。
- BFS 使用队列，递归 DFS 使用调用栈，迭代 DFS 使用显式栈。每次发现旧色邻格时立刻改色并加入待处理结构，避免同一格重复入队/栈。
- 正确性不变量：改色集合始终属于起点旧色连通分量；每次取出已发现格会检查全部四邻，终止时该分量已无未发现旧色邻居。
- 对全部短二值网格/种子/目标色的 46,098 组情况，以独立的连通分量不动点参考模型对照三种实现，并断言输入未变。
手动走一遍
图 [[1,1,0],[1,0,0]] 从 (0,0) 改成 2，结果 [[2,2,0],[2,0,0]]；右下角 0 不会因视觉相邻被误染。若从 (0,0) 改回 1，应直接返回同图。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
def flood_fill(image: list[list[int]], sr: int, sc: int,
new_color: int, method: str = "bfs") -> list[list[int]]:
"""Return a new four-neighbor image; methods: bfs, dfs, iterative_dfs."""
if not image or not image[0] or any(len(row) != len(image[0]) for row in image):
raise ValueError("image must be a nonempty rectangle")
rows, cols = len(image), len(image[0])
if not 0 <= sr < rows or not 0 <= sc < cols:
raise IndexError("seed outside image")
if method not in {"bfs", "dfs", "iterative_dfs"}:
raise ValueError("unknown method")
result = [row[:] for row in image]
original = result[sr][sc]
if original == new_color:
return result
def neighbors(r: int, c: int):
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= nr < rows and 0 <= nc < cols and result[nr][nc] == original:
yield nr, nc
result[sr][sc] = new_color
if method == "dfs":
def visit(r: int, c: int) -> None:
for nr, nc in neighbors(r, c):
result[nr][nc] = new_color
visit(nr, nc)
visit(sr, sc)
else:
pending = deque([(sr, sc)]) if method == "bfs" else [(sr, sc)]
while pending:
r, c = pending.popleft() if method == "bfs" else pending.pop()
for nr, nc in neighbors(r, c):
result[nr][nc] = new_color
pending.append((nr, nc))
return result
复杂度
R×C 格子至多访问一次，时间 O(RC)，输出拷贝 O(RC) 空间；BFS 队列/迭代 DFS 栈最坏 O(RC)，递归 DFS 调用深度最坏 O(RC)，大图可能触发语言递归限制。
易错点与追问
容易失分的边界
- 新旧颜色相同时未提前返回，访问判定失效。
- 出队后才改色，邻居可被重复入队很多次。
- 递归 DFS 在长蛇形分量上栈溢出。
- 把八邻接当标准四邻接，却没有问清变体。
- 返回新图的训练契约与原题可能要求原地修改混淆。
继续深挖
- 若图非常大且递归深度受限，你会选哪种写法？
- 若要求原地修改，空间复杂度如何变？
- 八邻接或带障碍掩码时邻居函数怎样改？
- 如果要返回分量面积和边界长度，遍历中如何统计？
