733. 图像渲染 - Flood Fill

🎯 问题描述（来源于LeetCode）

描述：
给定一个二维整数数组 image（表示图像，每个整数代表一个像素值），以及一个起点坐标 (sr, sc) 和一个新的颜色值 color。
从起点开始，将所有与起点四方向连通且颜色相同的像素（即同一连通区域）都改为 color，并返回修改后的图像。

说明：

连通区域定义为上下左右相连且原始颜色相同的像素集合。
如果起点的原始颜色已经等于 color，则无需修改。

示例：

示例 1：

1 2	输入: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2 输出: [[2,2,2],[2,2,0],[2,0,1]]

示例 2：

1 2	输入: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0 输出: [[0,0,0],[0,0,0]]

💻 解题思路

思路：深度优先搜索（DFS）

算法步骤

获取图像尺寸 m, n 和起点原始颜色 ori = image[sr][sc]。
如果 ori == color，直接返回原图（无需修改）。
定义递归函数 dfs(x, y)：
- 如果当前像素颜色不等于 ori，则返回（说明已处理或边界）。
- 将当前像素颜色改为 color。
- 对四个方向（上下左右）的邻居，若坐标合法且邻居颜色等于 ori，则递归调用 dfs。
从起点 (sr, sc) 开始调用 dfs。
返回修改后的 image。

代码实现

from typing import List

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        m, n = len(image), len(image[0])
        ori = image[sr][sc]
        if ori == color:
            return image
        
        def dfs(x, y):
            if image[x][y] != ori:
                return
            image[x][y] = color
            for dx, dy in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
                if 0 <= dx < m and 0 <= dy < n and image[dx][dy] == ori:
                    dfs(dx, dy)
        
        dfs(sr, sc)
        return image

📊 性能分析

时间复杂度： $O(m \times n)$ ，每个像素最多被访问一次。
空间复杂度： $O(L)$ ，其中 $L$ 是连通区域的大小（递归调用栈深度），最坏情况 $O(m \times n)$ 。

思考

本解法在递归前已判断 ori != color，因此染色后的像素颜色 color 一定不等于 ori，递归时不会再次进入已染色的格子，故不需要额外判断 image[x][y] == color。
也可以使用 BFS（队列）避免递归深度过大，尤其当图像尺寸很大时。
本题是经典的洪水填充算法（Flood Fill），广泛应用于画图软件的油漆桶工具。