Leetcode.733 图像渲染

题目链接

Leetcode.733 图像渲染 easy

题目描述

有一幅以 m x n的二维整数数组表示的图画 image，其中 image[i][j]表示该图画的像素值大小。

你也被给予三个整数 sr, sc和 newColor。你应该从像素 image[sr][sc]开始对图像进行 上色填充 。

为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor。

最后返回 经过上色渲染后的图像 。

示例 1:

输入: image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 在图像的正中间，(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。

示例 2:

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

提示：

• $m==image.length$
• $n==image[i].length$
• $1<=m,n<=50$
• $0<=image[i][j],newColor<2^{16}$
• $0<=sr<m$
• $0<=sc<n$

解法：dfs

我们用 $vis[i][j]$ 代表 $(i,j)$ 是否被方问过。初始为 false，访问之后设置为 true。

从 $(sr,sc)$ 开始，将所有颜色为 $image[sr][sc]$ 的位置涂成 $newColor$。

时间复杂度： $O(mn)$

C++代码：

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int m = image.size() , n = image[0].size();
        
        bool vis[m][n];
        memset(vis,false,sizeof vis);

        function<void(int,int,int)> dfs = [&](int i,int j,int c) -> void{
             //越界 或者 已经被访问过
            if(i < 0 || i >= m || j < 0 || j >= n || vis[i][j]) return;
            //颜色和初始的颜色不同 
            if(image[i][j] != c) return;

            image[i][j] = color;
            vis[i][j] = true;
            
            dfs(i + 1,j,c);
            dfs(i - 1,j,c);
            dfs(i,j + 1,c);
            dfs(i,j - 1,c);
        };

        dfs(sr,sc,image[sr][sc]);

        return image;
    }
};