LeetCode C++ 733. Flood Fill【DFS】シンプル

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535 ).
Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor , “flood fill” the image.
To perform a “flood fill”, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.
At the end, return the modified image.
Example 1:

Input: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: 
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected 
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.

Note:

The length of image and image[0] will be in the range [1, 50] .

The given starting pixel will satisfy 0 <= sr < image.length and 0 <= sc < image[0].length .

The value of each color in image[i][j] and newColor will be an integer in [0, 65535] .

題意:2次元整数配列で表される絵が与えられ、各整数はその絵の画素値の大きさを表し、数値は0から65535の間にある.次に、座標(sr, sc)が、画像レンダリングの開始を示す画素値( , )と、新しい色値newColorとを与える.次に、この画像を再着色し、初期座標から、その上下左右4方向の画素値が初期座標と同一の接続画素点を記録し、さらに、この4方向の条件に合致する画素点とそれらに対応する4方向の画素値が初期座標と同一の接続画素点を記録し、この過程を繰り返す.記録されたすべてのピクセルポイントのカラー値を新しいカラー値に変更します.最後に、カラーレンダリングされた画像を返します.
考え方:DFS、座標がある連通成分を求め、この連通成分上のすべての画素点に同じ色を塗る.
コード:

class Solution {
public:
    vector<vector<bool>> visited;
    vector<vector<int>> Move;
    int oldColor;
    void dfs(vector<vector<int>>& im, int sr, int sc, int nc) {
        visited[sr][sc] = true;
        im[sr][sc] = nc;
        for (int i = 0; i < 4; ++i) {
            int tr = sr + Move[i][0], tc = sc + Move[i][1];
            if (tr >= 0 && tr < im.size() && tc >= 0 && tc < im[0].size() && !visited[tr][tc] && im[tr][tc] == oldColor)
                dfs(im, tr, tc, nc);
        }
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        if (image.empty() || image[0].empty()) return image;
        oldColor = image[sr][sc];
        if (newColor == oldColor) return image;
        
        int m = image.size(), n = image[0].size();
        Move = {{-1,  0}, {1, 0}, {0, -1}, {0, 1}};
        visited.resize(m);
        for (int i = 0; i < m; ++i) visited[i].resize(n);
        dfs(image, sr, sc, newColor);
        return image;
    }
};

以下のように書くこともできます.時間効率が高く、空間効率が高く、余分な空間を使用しません.

class Solution {
public:
    void dfs(vector<vector<int>>& im, int r, int c, int newColor, int oldColor) {
        if (r < 0 || r >= im.size() || c < 0 || c >= im[0].size() || im[r][c] == newColor || im[r][c] != oldColor)
            return;
        im[r][c] = newColor;
        dfs(im, r + 1, c, newColor, oldColor);
        dfs(im, r, c + 1, newColor, oldColor);
        dfs(im, r - 1, c, newColor, oldColor);
        dfs(im, r, c - 1, newColor, oldColor);
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        if (image.empty() || image[0].empty()) return image;
        dfs(image, sr, sc, newColor, image[sr][sc]);
        return image;
    }
};

効率:

    ：12 ms,     C++       91.99%    
    ：13.6 MB,     C++       90.72%