Flood Fill
图像是由整数构成的网格，每个数字表示一个像素的颜色。你会得到一个由行组成的列表、起始像素所在的行 sr 和列 sc，以及一种新的 color。重新绘制包含起始像素的区域：将所有与起始像素颜色相同，并且可以通过同色像素向上、向下、向左或向右移动到达的像素重新着色。返回重新绘制后的图像。
函数
- imageinteger-2d-array
- 将图像表示为一个由行组成的列表，每个像素对应一个数字
- srinteger
- 起始像素所在的行，计数从 0 开始
- scinteger
- 起始像素所在的列，从 0 开始计数
- colorinteger
- 该区域的新颜色
- 返回值integer-2d-array
- 该区域重新绘制后的图像
约束条件
1 ≤ image.length ≤ 801 ≤ image[i].length ≤ 80- 每一行的长度都相同。
0 ≤ image[i][j], color ≤ 655350 ≤ sr < image.length和0 ≤ sc < image[0].length
示例
- 输入
- image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]sr = 0sc = 0color = 5
- 输出
- [[5, 5, 0], [5, 0, 5], [5, 5, 5]]
- 解释
- 起点的颜色是 1。所有 7 个 1 都通过相邻的 1 与它相连，沿着左侧列向下、沿着底行前进，再沿着右侧边缘向上，所以它们都会变成 5。两个 0 保持原来的颜色。
- 输入
- image = [[3, 3, 3], [3, 7, 3], [3, 3, 3]]sr = 1sc = 1color = 7
- 输出
- [[3, 3, 3], [3, 7, 3], [3, 3, 3]]
- 解释
- 起始位置已经是颜色 7，因此把它所在的区域涂成 7 不会有任何变化，图像会恢复原样。
- 输入
- image = [[2, 2, 4, 4], [4, 2, 2, 4], [4, 4, 2, 2]]sr = 2sc = 3color = 9
- 输出
- [[9, 9, 4, 4], [4, 9, 9, 4], [4, 4, 9, 9]]
- 解释
- 这些 2 从右下角到左上角排成阶梯状，每一级都与下一级共用一条边，因此它们都会变成 9。这些 4 分成两块互不相连的区域，颜色保持不变。
进阶
如果仅在角上相接的像素也算作连通，你的答案会有什么变化？
提示
逐个打开提示，每个都会多透露一点。
哪些像素可能发生变化？只有与起始像素颜色相同的像素，并且只有当一条由这种颜色组成的路径将它们与起始像素连接起来时才会发生变化。
把每个像素看作一个节点，当两个像素共用一条边且颜色都与起始颜色相同时，就将它们连接起来。区域就是从起点能够到达的所有像素，因此可以用任何图搜索算法找到它。
保留一个待查看像素的栈。在推入像素时立即为它着色，这样，已着色的像素就不再匹配，也不会再次被推入。先检查新颜色是否与旧颜色相同。
题解
把像素看作节点：如果两个像素共享一条边，且颜色与起始像素相同，就将它们连接起来。该区域是包含起始像素的连通部分，从起始像素出发，只沿着这种颜色搜索，就能找到它。注意，新颜色可能与旧颜色相同；蜿蜒很长的区域也可能导致递归溢出。
递归深度优先搜索
结果正确，但无法在最大的测试中运行完毕
思路
paint(r, c) 会为图像中颜色仍为旧颜色的像素着色，然后对它的四个相邻像素调用自身。区域中的每个像素都通过一条由旧颜色像素组成的路径与起点相连，这些调用会沿着这条路径进行。先着色再调用可以阻止扩散绕回，因为已着色的像素不再匹配。只有颜色不同时这种方法才有效，所以颜色相同时要提前返回。
递归的深度取决于它所沿路径的长度。在一张 80 × 80 的图像中，一条宽度为 1 像素的蛇形路径约有 3,200 个像素，因此调用会嵌套约 3,200 层；图像更大时，任何调用栈都会耗尽。
算法
- 读取
old = image[sr][sc]。如果old等于color，则返回图像。 - 定义
paint(r, c)：如果(r, c)超出图像范围，或其颜色不是old，则返回。 - 否则，将
image[r][c] = color，并对上方、下方、左侧和右侧的像素调用paint。 - 调用
paint(sr, sc)并返回图像。
def floodFill(image, sr, sc, color):
old = image[sr][sc]
if old == color:
return image
rows, cols = len(image), len(image[0])
def paint(r, c):
# Stop outside the image and at any pixel that is not the old color.
if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != old:
return
image[r][c] = color
paint(r + 1, c)
paint(r - 1, c)
paint(r, c + 1)
paint(r, c - 1)
paint(sr, sc)
return image使用显式栈进行深度优先搜索
思路
用你自己的栈来执行同样的遍历，而不是使用调用栈。压入像素时就给它上色，而不是弹出时。这样，颜色检查也能用来检查是否已访问：每个像素只会进入栈一次，而且你不需要单独的标记网格。
区域中的每个像素只会被压入一次，并检查四个相邻像素，因此时间复杂度为 O(m × n)。栈存储在普通内存中，所以长达 3,200 个像素的蛇形区域也不成问题。
算法
- 读取
old = image[sr][sc]。如果old等于color，则返回图像。 - 为
(sr, sc)着色，并将它压入栈中。 - 弹出一个像素，并查看它的四个邻居。
- 对于图像内颜色为
old的每个邻居，为它着色并将它压入栈中。 - 栈为空时，返回图像。
def floodFill(image, sr, sc, color):
old = image[sr][sc]
# Painting a region its own color changes nothing. Returning here also
# stops the search from pushing the same cells forever.
if old == color:
return image
rows, cols = len(image), len(image[0])
image[sr][sc] = color
stack = [(sr, sc)]
while stack:
r, c = stack.pop()
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 image[nr][nc] == old:
# Paint on push: a painted cell no longer matches old,
# so it can never be pushed twice.
image[nr][nc] = color
stack.append((nr, nc))
return image
易错点和边界情况
- 涂色后再读取
image[sr][sc]。先保存旧颜色，否则每个相邻像素都会与新颜色比较。 - 统计对角线方向的相邻像素。只在角上接触的像素并不相连。
- 检查相邻像素的颜色后，才检查它是否位于图像范围内。先测试
0 ≤ row < rows和0 ≤ col < cols。 - 在 Python 中递归，默认的 1,000 次调用限制会在上面的蛇形图案处导致程序停止。
- 将图像中所有旧颜色的像素都涂色。与起点隔开的同色像素会保留原来的颜色。
常见问题3
Flood Fill 的时间复杂度是多少？
对于有 m 行、n 列的图像，时间复杂度为 O(m × n)。区域中的每个像素都会被推入栈一次，并检查四个相邻像素；区域外的像素只会作为相邻像素被检查。当整张图像都属于同一个区域时，栈最多会存放 m × n 个像素。
洪水填充应该使用 BFS 还是 DFS？
两种方法的时间复杂度都是 O(m × n)。无论按哪种顺序遍历，区域都相同，所以队列（广度优先）和栈（深度优先）都会填充相同的像素。选择写起来更简洁的方法，并避免在大图像上使用递归。
为什么当新颜色与旧颜色相同时，Flood Fill 会陷入无限循环？
通常的解决方法会把“仍然是旧颜色”视为“尚未访问”。当新颜色等于旧颜色时，填色不会改变任何内容，因此相邻像素会不断把彼此推回栈中，形成无限循环。这种情况下直接返回原图即可，它已经是正确答案。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def floodFill(image, sr, sc, color):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]] sr = 0 sc = 0 color = 5
预期输出
[[5, 5, 0], [5, 0, 5], [5, 5, 5]]