图像渲染

🟢 Easy · 🏷️ 数组、DFS、矩阵 · LeetCode#733

📖 题目

给一张二维图片、一个起始坐标 (sr, sc) 和新颜色 color，把从起点出发、颜色相同且四方向相连的像素全部换成新颜色（就是画图工具的"油漆桶"）。

输入	输出
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]]

💡 思路

跟树的 DFS 是同一件事，只是把"左右两个子节点"换成了"上下左右四个邻居"：

	树的 DFS	网格 DFS
终止条件	节点为空	越界 或 颜色不对
处理	当前节点	染色
递归方向	左、右（2个）	上、下、左、右（4个）

容易踩的坑：染色本身就相当于"标记已访问"——染过之后颜色不再等于 original_color，自然不会被重复访问。但如果起始颜色和新颜色相同（original_color == color），染完颜色没变，标记就失效了，邻居会一直互相触发，死循环。所以要先判断这种情况，直接返回。

💻 代码

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        original_color = image[sr][sc]
        if original_color == color:
            return image
        rows, cols = len(image), len(image[0])

        def dfs(row, col):
            if 0 <= row < rows and 0 <= col < cols and image[row][col] == original_color:
                image[row][col] = color
                dfs(row + 1, col)
                dfs(row - 1, col)
                dfs(row, col + 1)
                dfs(row, col - 1)

        dfs(sr, sc)
        return image

时间复杂度 O(m × n)，每个像素最多访问一次；空间复杂度最坏 O(m × n)（全部同色时的递归栈深度）。这套"网格 DFS"模板后面遇到岛屿类问题会反复用到。