[LeetCode] 733. Flood Fill

You are given an image represented by an m x n grid of integers image, where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color. Your task is to perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill:

Begin with the starting pixel and change its color to color.
Perform the same process for each pixel that is directly adjacent (pixels that share a side with the original pixel, either horizontally or vertically) and shares the same color as the starting pixel.
Keep repeating this process by checking neighboring pixels of the updated pixels and modifying their color if it matches the original color of the starting pixel.
The process stops when there are no more adjacent pixels of the original color to update.
Return the modified image after performing the flood fill.

Example 1:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

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.

Note the bottom corner is not colored 2, because it is not horizontally or vertically connected to the starting pixel.

Example 2:
Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
Output: [[0,0,0],[0,0,0]]

Explanation:
The starting pixel is already colored with 0, which is the same as the target color. Therefore, no changes are made to the image.

Constraints:
m == image.length
n == image[i].length
1 <= m, n <= 50
0 <= image[i][j], color < 216
0 <= sr < m
0 <= sc < n

图像渲染。

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flood-fill
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这一题跟之前的695和547很类似，是矩阵类型的基础题。题目给了起始位置和需要更新的颜色 newColor，思路是用 DFS 判断四个方向的坐标上是否需要被更新颜色。

如果

• 超出矩阵范围
• 或者颜色跟初始坐标上的颜色（image[sr][sc]）不同
• 又或者已经被染色过了（已经是newColor）

则直接 return。同时如果一开始给的坐标也是被染色过了的（newColor），就直接退出了，无需任何操作。因为染色的动作一定是要从当前坐标开始被触发的。

复杂度

时间O(mn)
空间O(n) - 栈空间

代码

BFS

Java实现

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int ori = image[sr][sc];
        // corner case
        if (ori == color) {
            return image;
        }

        // normal case
        int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
        image[sr][sc] = color;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] { sr, sc });
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] dir : dirs) {
                int r = cur[0] + dir[0];
                int c = cur[1] + dir[1];
                if (r >= 0 && r < image.length && c >= 0 && c < image[0].length && image[r][c] == ori) {
                    image[r][c] = color;
                    queue.offer(new int[] { r, c });
                }
            }
        }
        return image;
    }
}

DFS

Java实现

class Solution {
    int m;
    int n;
    
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        m = image.length;
        n = image[0].length;
        int ori = image[sr][sc];
        if (ori == color) {
            return image;
        }
        dfs(image, sr, sc, ori, color);
        return image;
    }

    private void dfs(int[][] image, int i, int j, int ori, int color) {
        if (i < 0 || j < 0 || i >= m || j >= n || image[i][j] != ori) {
            return;
        }
        image[i][j] = color;
        dfs(image, i - 1, j, ori, color);
        dfs(image, i + 1, j, ori, color);
        dfs(image, i, j - 1, ori, color);
        dfs(image, i, j + 1, ori, color);
    }
}