LeetCode 733. 图像渲染

◎

本节目标

用同色网格 DFS 将起点所在连通区域改成目标颜色。

这道题是网格与状态图搜索中最小的连通块遍历模型：从起点出发，只扩展原来颜色相同的四邻格，并统一改成目标颜色。

查看 LeetCode 原题

朴素思路与瓶颈

可以不断扫描整张图，找到与起点同色、又挨着已改色格子的像素后再改色。这样每扩展一层都可能重新扫描整张图，区域很大时重复工作明显。DFS 直接沿相邻格深入，每个可达格只处理一次。

状态与永久访问

状态是坐标 (row, col)；相邻状态是上下左右四格。sourceColor 固定为起点的原颜色，只有颜色仍等于它的格子才能访问。将格子改为目标颜色就是访问标记，因此不需要单独的 visited 数组，也不应恢复颜色。

若原颜色已经等于目标颜色，改色不再能区分“未访问”和“已访问”。此时必须直接返回，否则递归会在同色格之间往返。

代码实现

两种实现都保留 floodFill 平台接口，先记录原颜色，再以改色作为 DFS 的永久访问标记。方法会原地修改 image，并返回这张同一个图像。

C++

C++17

#include <vector>
using namespace std;

class Solution {
private:
    int rows = 0;
    int cols = 0;
    int sourceColor = 0;
    int targetColor = 0;

    void dfs(vector<vector<int>>& image, int row, int col) {
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            return;
        }
        if (image[row][col] != sourceColor) {
            return;
        }

        // 改色即标记访问，避免沿同色区域反复递归。
        image[row][col] = targetColor;
        dfs(image, row - 1, col);
        dfs(image, row + 1, col);
        dfs(image, row, col - 1);
        dfs(image, row, col + 1);
    }

public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        sourceColor = image[sr][sc];
        if (sourceColor == color) {
            return image;
        }

        rows = static_cast<int>(image.size());
        cols = static_cast<int>(image[0].size());
        targetColor = color;
        dfs(image, sr, sc);
        return image;
    }
};

Python

Python 3

class Solution:
    def floodFill(
        self, image: list[list[int]], sr: int, sc: int, color: int
    ) -> list[list[int]]:
        source_color = image[sr][sc]
        if source_color == color:
            return image

        rows = len(image)
        cols = len(image[0])
        stack = [(sr, sc)]
        image[sr][sc] = color

        while stack:
            row, col = stack.pop()
            for row_change, col_change in (
                (-1, 0),
                (1, 0),
                (0, -1),
                (0, 1),
            ):
                next_row = row + row_change
                next_col = col + col_change
                if (
                    0 <= next_row < rows
                    and 0 <= next_col < cols
                    and image[next_row][next_col] == source_color
                ):
                    # 入栈前改色，避免同一格被多个邻居重复加入。
                    image[next_row][next_col] = color
                    stack.append((next_row, next_col))
        return image

复杂度分析

设图像大小为 m × n。每个格子至多访问一次，时间复杂度为 O(mn)；递归栈最坏为 O(mn)。除递归栈外，直接在图像上标记，不额外建立访问数组。

易错点

• 用目标颜色而不是原颜色判断能否继续，导致边界判断失真。
• 忘记处理原颜色等于目标颜色，产生无限递归。
• 访问对角格；本题只允许四个正交方向。
• 递归返回后恢复颜色，导致同一像素被重复处理。

模式迁移

当题目要求从一个种子状态扩散到同类邻居时，可先尝试这种“原值同时充当访问条件”的 DFS。若不能修改原输入，再把改色替换成独立的 visited 集合或矩阵。