# 【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++`