leetcode
leetcode 2801 ~ 2850
颜色填充

颜色填充

难度:

标签:

题目描述

Implement the "paint fill" function that one might see on many image editing programs. That is, given a screen (represented by a two-dimensional array of colors), a point, and a new color, fill in the surrounding area until the color changes from the original color.

Example1:

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

代码结果

运行时间: 19 ms, 内存: 16.1 MB

/*
 * 题目思路：
 * 1. 检查初始坐标点的颜色是否已经是新颜色，如果是则不需要改变。
 * 2. 使用深度优先搜索（DFS）从初始坐标点开始遍历所有相连的同颜色像素，并将其颜色改为新颜色。
 * 3. 使用Java Stream API的方式处理图像的颜色填充。
 */
import java.util.Arrays;

public class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int oldColor = image[sr][sc];
        if (oldColor != newColor) {
            fill(image, sr, sc, oldColor, newColor);
        }
        return image;
    }

    private void fill(int[][] image, int sr, int sc, int oldColor, int newColor) {
        if (sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length || image[sr][sc] != oldColor) {
            return;
        }
        image[sr][sc] = newColor;
        Arrays.asList(
            new int[]{sr - 1, sc},
            new int[]{sr + 1, sc},
            new int[]{sr, sc - 1},
            new int[]{sr, sc + 1}
        ).stream().filter(coord -> coord[0] >= 0 && coord[0] < image.length && coord[1] >= 0 && coord[1] < image[0].length)
        .forEach(coord -> fill(image, coord[0], coord[1], oldColor, newColor));
    }
}

解释

方法:

此题解采用了广度优先搜索（BFS）方法。首先，从给定的起始点 (sr, sc) 开始，检查此点的颜色是否已经是新颜色，如果是，则直接返回图像；否则，使用队列来进行BFS。将起始点加入队列。在BFS过程中，从队列中取出点，将其颜色更改为新颜色，并检查其四个方向上的相邻点。如果相邻点的颜色与起始点的旧颜色相同，且未越界，则将这些点加入队列以便后续处理。重复此过程直至队列为空，最后返回修改后的图像。

时间复杂度:

O(m*n)

空间复杂度:

O(m*n)

代码细节讲解

🦆
在实现BFS时，如何确保不会将已经检查过的像素点重复加入队列中，从而避免无效的重复操作？
▷
在BFS实现中，确保不重复加入已检查的像素点是通过立即将点的颜色更改为新颜色来实现的。当一个像素点的颜色被改变后，这个点就不会再次被加入队列中，因为后续的颜色检查（是否与旧颜色相同）将会失败。这种方法同时处理了点的访问记录和颜色修改，简化了逻辑且提高了效率。
🦆
为什么在开始BFS之前需要检查起始点的颜色是否已经是新颜色？这一步是否对所有情况都是必要的？
▷
在开始BFS之前检查起始点的颜色是否已经是新颜色是必要的，因为如果起始点已经是新颜色，那么没有必要执行任何颜色填充操作。这一步可以避免不必要的操作，如初始化队列、进行颜色检查和修改等。此步骤对所有情况都是必要的，它是优化效率的一种简单且有效的方式。
🦆
你提到了BFS将从起始点检查四个方向，但如果碰到已经是新颜色的相邻点，处理方式是如何的？
▷
在BFS过程中，如果碰到已经是新颜色的相邻点，这个点将不会被加入队列中。在检查一个点是否应该加入队列时，会比较该点的颜色与旧颜色是否相同。由于点的颜色已经是新颜色，它不符合加入队列的条件（颜色与旧颜色相同），因此不会进行任何操作。这样确保只有颜色需要被更改的点才会被处理。

相关问题

递归乘法堆箱子