# 733. Flood Fill

[**733. Flood Fill**](https://leetcode.com/problems/flood-fill/description/)

An image is represented by an `m x n` integer grid `image` where `image[i][j]` represents the pixel value of the image.

You are also given three integers `sr`, `sc`, and `color`. You should perform a **flood fill** on the image starting from the pixel `image[sr][sc]`.

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), and so on. Replace the color of all of the aforementioned pixels with `color`.

Return *the modified image after performing the flood fill*.

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/06/01/flood1-grid.jpg)

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

***My Solutions:***

这道题的意思是image\[sr]\[sc]出发，检查所有相邻的格子(当前点以及这个点连接的四个点)，如果格子的颜色和初始格子颜色相同，改变相邻的格子的颜色变成new color。

用dfs的思想，依次检查每个cell的上下左右。

```
class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int oldColor = image[sr][sc];
        if (oldColor != color) dfs(image, sr, sc, oldColor, color);
        return image;
    }
    
    private void dfs(int[][] image, int r, int c, int color, int newColor) {
        if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) return;
        if (image[r][c] == color) {
            image[r][c] = newColor;
            dfs(image, r + 1, c, color, newColor);
            dfs(image, r - 1, c, color, newColor);
            dfs(image, r, c + 1, color, newColor);
            dfs(image, r, c - 1, color, newColor);
        }
    }
}
```
