洪水填充（Flood Fill）是一种基于深度优先搜索（DFS）或广度优先搜索（BFS）的算法，用于标记或遍历与起始点相连的特定区域。常见应用包括图像处理中的颜色填充、矩阵中的连通区域标记等。

算法核心思想

1. 递归实现DFS
   从起始点出发，递归访问其相邻的未访问节点，直到所有连通区域被标记。
   示例代码（矩阵中的四连通填充）：

   def flood_fill(matrix, x, y, target_color, new_color):
       if x < 0 or x >= len(matrix) or y < 0 or y >= len(matrix[0]):
           return
       if matrix[x][y] != target_color:
           return
       matrix[x][y] = new_color
       flood_fill(matrix, x+1, y, target_color, new_color)  # 下
       flood_fill(matrix, x-1, y, target_color, new_color)  # 上
       flood_fill(matrix, x, y+1, target_color, new_color)  # 右
       flood_fill(matrix, x, y-1, target_color, new_color)  # 左
   

2. 栈实现非递归DFS
   递归可能引发栈溢出，可用显式栈替代：

   def flood_fill_stack(matrix, x, y, target_color, new_color):
       stack = [(x, y)]
       while stack:
           x, y = stack.pop()
           if matrix[x][y] != target_color:
               continue
           matrix[x][y] = new_color
           for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
               nx, ny = x + dx, y + dy
               if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]):
                   stack.append((nx, ny))
   

边界条件与优化

1. 终止条件
   需检查坐标是否越界、当前颜色是否为目标颜色。若填充颜色与目标颜色相同，需提前终止以避免无限循环。

2. 性能优化

   • 访问标记：对已访问的点进行标记，避免重复处理（如使用辅助矩阵或修改原矩阵）。
   • 方向扩展：四连通（上下左右）或八连通（包含对角线）根据需求调整方向数组。

典型例题

问题：LeetCode 733. 图像渲染
给定一个二维矩阵表示图像，从起始像素(sr, sc)开始，将所有与起始点颜色相同的连通区域填充为新颜色。

解法：

def floodFill(image, sr, sc, newColor):
    target = image[sr][sc]
    if target == newColor:
        return image
    stack = [(sr, sc)]
    while stack:
        r, c = stack.pop()
        if image[r][c] == target:
            image[r][c] = newColor
            for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < len(image) and 0 <= nc < len(image[0]):
                    stack.append((nr, nc))
    return image

复杂度分析

• 时间复杂度：O(M×N)，M和N为矩阵的行列数，每个节点最多访问一次。
• 空间复杂度：O(M×N)，递归栈或显式栈的最坏情况空间占用。