【LeetCode】 733. Flood Fill

Description

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.

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].

一個image由一個二維的整數陣列所表示，每個整數代表圖像中像素點的值(0到65535)。

給予一個座標點(sr, sc)代表洪水填充的起始點(直排和橫列)，和一個像素點的值newColor，請使用"洪水填充演算法"填補這個圖片。

要完成洪水填充法，從起始點開始，如果周圍四格相鄰的像素點和起始點是相同顏色的，將它們加入到起始點，並且再去加入和它們同樣顏色的鄰近點，如此不停做下去。用新的顏色替換掉前面提到的每個像素點。

最後，回傳修改後的圖像。

提示：

• image的長度和image[0]的範圍落於[1, 50]。
• 給予的起始點滿足0 <= sr < image.length and 0 <= sc < image[0].length。
• image[i][j]和newColor的顏色的值會是整數並落於[0, 65535]的範圍中。

Example:

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.

Solution

• 我們要做的洪水演算法基本上就是小畫家中"填充"的功能，可以用DFS或是BFS輕鬆完成。
• 由於DFS不須使用queue就可以實作，我們這邊使用DFS來完成。
• 要完成的事情就是檢查該點是否為相同顏色，如果是就遞迴去跑四周的格子。
  • 記得檢查是否超出邊界。
  • 記得檢查舊的顏色和新的顏色是否相同(如果相同就會變成無窮迴圈)。

Code

class Solution {
public:
    void DFS(vector<vector<int>>& image, int x, int y, int oldColor, int newColor)
    {
        if(image[y][x] == oldColor)
        {
            image[y][x] = newColor;
            if(x > 0)
                DFS(image, x - 1, y, oldColor, newColor);
            if(x < image[0].size() - 1)
                DFS(image, x + 1, y, oldColor, newColor);
            if(y > 0)
                DFS(image, x, y - 1, oldColor, newColor);
            if(y < image.size() - 1)
                DFS(image, x, y + 1, oldColor, newColor);
        }
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        if(image[sr][sc] == newColor)
            return image;
        DFS(image, sc, sr, image[sr][sc], newColor);
        return image;
    }
};

tags: LeetCode C++