CC++ & Algorithm

Python Flood Fill 算法

困难2
语言版本：C++Python
概述：用“给小白兔涂色”的比喻，讲解Flood Fill算法如何像油漆桶一样填充相连的区域，并给出Python代码示例。

用Python实现Flood Fill：像魔法油漆桶一样填充相连区域

你有没有在画图软件里点过“油漆桶”工具？一点下去，整个同颜色的区域就“唰”一下变成了新颜色。这个超好用的功能，背后就用到了Flood Fill（洪水填充）算法。今天我们就用Python把它写出来，像变魔术一样给格子板涂色！

什么是Flood Fill？——从一滴水到一片海洋

想象你有一个方格本，每个格子要么是白色（0），要么是黄色（1）。现在你用手指按住一个黄色格子，然后说“变蓝！”，那么所有和这个格子“手拉手”连在一起的黄色格子都会变成蓝色。这里的关键是“连在一起”——只有上下左右相邻（不能斜着）的黄色格子才算。Flood Fill就是从这个起点出发，像水漫金山一样向四周蔓延，把所有能到达的同颜色格子都染上新颜色。

生活中还有哪里用到它？比如：

  • 地图涂色：给地图上某个国家的所有区域填充同一种颜色。
  • 游戏关卡：很多消除游戏里，点击一块相同颜色的宝石，周围相同颜色的宝石就会一起消失（也是Flood Fill）。
  • 图像处理：抠图时选中某个区域，自动标记出连在一起的像素。

第一步：用数字表示我们的格子板

我们用一个二维列表（列表里套列表）来表示格子板。每个数字代表一种颜色：

  • 0 = 白色
  • 1 = 黄色
  • 2 = 蓝色

举个简单的例子，这是一个 3 行 4 列的格子板：

# 格子板：白色(0)，黄色(1)
grid = [
    [0, 1, 0, 0],  # 第0行
    [1, 1, 1, 0],  # 第1行
    [0, 1, 0, 0],  # 第2行
    [0, 0, 0, 0],  # 第3行
]

从坐标 (1,1)（第1行第1列，最左上角是第0行第0列）的黄色格子出发，想把这片黄色区域全部变成蓝色。

第二步：递归——“水”是怎么漫开的？

Flood Fill最直观的做法是递归，就像一个人站在起点，然后模仿水流：

  1. 先看看自己有没有越界（跑去格子外面了？），如果越界就停止。
  2. 检查自己是不是我们要找的颜色（黄色），如果不是（比如已经是蓝色或白色），就不处理。
  3. 把自己染成新颜色（蓝色）。
  4. 分别向上、下、左、右四个方向派去“分身”，让它们重复做同样的事。

这个过程也叫深度优先搜索（DFS）——一条路走到黑，再回头走另一条。就像用一根水管，先往一个方向拼命冲，直到碰到墙再拐回来。

第三步：写代码——完整的Flood Fill函数

下面是一个完整的Python实现，每个变量都加了中文注释，方便理解：

def flood_fill(grid, x, y, new_color):
    """
    从格子板 grid 的 (x, y) 位置开始，
    把所有与 (x, y) 颜色相同且连通的格子都变成 new_color。
    
    grid:     二维列表，表示格子板
    x, y:     起始行列（行号x，列号y）
    new_color: 要填充的新颜色数字
    """
    old_color = grid[x][y]  # 记录起始格子的旧颜色
    # 如果新颜色和旧颜色一样，就不用改了，否则会无限循环！
    if old_color == new_color:
        return
    
    # 定义内部的递归函数fill
    def fill(x, y):
        # 检查是否越界（行号或列号超出范围）
        if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):
            return
        # 检查当前格子颜色是否等于旧颜色（不是要找的颜色就跳过）
        if grid[x][y] != old_color:
            return
        # 染色：把当前格子变成新颜色
        grid[x][y] = new_color
        # 向四个方向递归
        fill(x-1, y)  # 上
        fill(x+1, y)  # 下
        fill(x, y-1)  # 左
        fill(x, y+1)  # 右
    
    # 从起点开始填充
    fill(x, y)


# ========== 测试代码 ==========
# 定义格子板（白色=0，黄色=1）
game_board = [
    [0, 1, 0, 0],  # 第0行
    [1, 1, 1, 0],  # 第1行
    [0, 1, 0, 0],  # 第2行
    [0, 0, 0, 0],  # 第3行
]

print("填充前的格子板：")
for row in game_board:
    print(row)

# 从 (1,1) 开始填充，新颜色为2（蓝色）
flood_fill(game_board, 1, 1, 2)

print("\n填充后的格子板（黄色→蓝色）：")
for row in game_board:
    print(row)

运行结果：

填充前的格子板：
[0, 1, 0, 0]
[1, 1, 1, 0]
[0, 1, 0, 0]
[0, 0, 0, 0]

填充后的格子板（黄色→蓝色）：
[0, 2, 0, 0]
[2, 2, 2, 0]
[0, 2, 0, 0]
[0, 0, 0, 0]

所有连在一起的黄色（1）都变成了蓝色（2）！那些白色格子因为颜色不匹配，没有被“感染”。

常见错误与避坑指南

新手写Flood Fill时，容易踩下面几个坑：

错误1：忘记检查旧颜色和新颜色是否相同

如果你从黄色格子开始，偏偏新颜色也是黄色，那么old_color == new_color就会成立，如果不提前return，递归会反复染同一个格子，导致无限循环，程序崩溃。所以第一件事就要判断并退出。

错误2：忘记检查越界

递归时如果x或y变成负数或者超过格子板大小，就会报IndexError。一定要在函数开头先检查坐标是否合法。

错误3：把斜对角也算成连通

Flood Fill只考虑上下左右四个方向，不包括左上、右上、左下、右下。如果你不小心把八个方向都写了，就会把不是同色的对角格子也染上，结果就不是你想要的区域了。

错误4：递归太深导致栈溢出

如果格子板非常大（比如1000×1000），递归层数可能超过Python默认的递归深度（约1000层），程序会报RecursionError。这时候就需要改用**栈（Stack）来模拟递归，或者用队列（Queue）**实现广度优先搜索（BFS）。下面就来介绍用栈实现的方法。

进阶：用栈（非递归）实现Flood Fill——告别栈溢出

既然递归容易爆炸，我们可以用自己管理的“栈”来模拟递归的过程。思路还是一样的：从起点出发，把待处理的坐标放进栈里，然后循环处理，直到栈为空。

def flood_fill_stack(grid, x, y, new_color):
    """
    用栈实现Flood Fill，避免递归深度限制
    """
    old_color = grid[x][y]  # 旧颜色
    if old_color == new_color:
        return
    
    rows = len(grid)        # 格子板行数
    cols = len(grid[0])     # 格子板列数
    
    stack = [(x, y)]        # 栈：存放待处理的坐标，初始放入起点
    
    while stack:            # 只要栈不为空，就继续处理
        cur_x, cur_y = stack.pop()  # 取出一个坐标（后进先出）
        
        # 检查越界和颜色是否匹配
        if cur_x < 0 or cur_x >= rows or cur_y < 0 or cur_y >= cols:
            continue
        if grid[cur_x][cur_y] != old_color:
            continue
        
        # 染色
        grid[cur_x][cur_y] = new_color
        
        # 把上下左右四个邻居加入栈
        stack.append((cur_x - 1, cur_y))  # 上
        stack.append((cur_x + 1, cur_y))  # 下
        stack.append((cur_x, cur_y - 1))  # 左
        stack.append((cur_x, cur_y + 1))  # 右

这个方法用栈代替了递归调用，原理一模一样，但不会受递归深度限制。另外，如果我们把栈换成队列（用collections.deque），就变成了广度优先搜索（BFS），会一层一层地向外扩散，就像是同心圆一样展开。BFS的代码也很相似，只是把pop()换成popleft()（左端出队）。想挑战的同学可以自己试试。

生活中的扩展：用Flood Fill做“填色游戏”

你可以把Flood Fill和画图结合起来，做一个简单的“填色小游戏”。比如：

  1. 先用数字数组画一幅黑白线稿（0=白色，1=黑色边框）。
  2. 允许用户输入点击坐标，然后用Flood Fill把白色区域染成喜欢的颜色。
  3. 连续点不同区域，就能创作一幅彩色画啦！

如果想做更高级的，还可以添加“容差”（比如相近颜色都算），或者结合鼠标事件实时交互。

相关知识点指引

  • 深度优先搜索（DFS）：Flood Fill的递归实现就是DFS的一种应用。学会了DFS，你还能解决迷宫寻路、图的连通分量等更多问题。
  • 广度优先搜索（BFS）：用队列实现的Flood Fill就是BFS，它常用于求最短路径，比如计算从起点到某个点的最少步数。
  • 栈和队列：理解这两种数据结构后，你可以轻松写出非递归版本的算法。
  • 递归与递归深度：知道了递归的优缺点，以后遇到类似“分形、树形结构”的问题时，你会更好选择是用递归还是用迭代。

Flood Fill是图遍历算法中最简单、最可爱的例子。下次当你打开画图软件点下油漆桶时，就可以自豪地说：“我知道它是怎么工作的！”

例题精讲

1单选题

若使用递归方式实现Flood Fill算法，在处理大尺寸图像时最可能遇到什么问题？

A栈溢出
B时间复杂度退化为O(n^2)
C空间复杂度为零
D无法处理边界像素
2单选题

在Flood Fill算法中，必须执行哪一步才能避免死循环（重复访问同一像素）？

A标记已访问像素
B使用队列存储坐标
C检查像素是否在边界内
D每次循环都调用递归
3判断题

Flood Fill算法的时间复杂度总是与整个图像的像素总数成正比。

4填空题
以下是用队列实现的Flood Fill函数，请填写缺少的条件，使其正确运行：

def flood_fill(image, sr, sc, new_color):
    old_color = image[sr][sc]
    if old_color == new_color:
        return image
    rows, cols = len(image), len(image[0])
    from collections import deque
    q = deque()
    q.append((sr, sc))
    while q:
        r, c = q.popleft()
        if 0 <= r < rows and 0 <= c < cols and image[r][c] == ___:
            image[r][c] = new_color
            for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                q.append((r+dr, c+dc))
    return image
5填空题
以下是用递归实现的Flood Fill函数，请填写缺少的条件，使其正确运行：

def flood_fill(image, x, y, new_color, old_color):
    rows, cols = len(image), len(image[0])
    if x < 0 or x >= rows or y < 0 or y >= cols or image[x][y] != ___:
        return
    image[x][y] = new_color
    flood_fill(image, x+1, y, new_color, old_color)
    flood_fill(image, x-1, y, new_color, old_color)
    flood_fill(image, x, y+1, new_color, old_color)
    flood_fill(image, x, y-1, new_color, old_color)