颜色填充

难度: Easy

编写函数，实现许多图片编辑软件都支持的「颜色填充」功能。

待填充的图像用二维数组 image 表示，元素为初始颜色值。初始坐标点的行坐标为 sr 列坐标为 sc。需要填充的新颜色为 newColor 。

「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。

请用新颜色填充初始坐标点的周围区域，并返回填充后的图像。

示例：

输入：
image = [[1,1,1],[1,1,0],[1,0,1]] 
sr = 1, sc = 1, newColor = 2
输出：[[2,2,2],[2,2,0],[2,0,1]]
解释: 
初始坐标点位于图像的正中间，坐标 (sr,sc)=(1,1) 。
初始坐标点周围区域上所有符合条件的像素点的颜色都被更改成 2 。
注意，右下角的像素没有更改为 2 ，因为它不属于初始坐标点的周围区域。

提示：

image 和 image[0] 的长度均在范围 [1, 50] 内。
初始坐标点 (sr,sc) 满足 0 <= sr < image.length 和 0 <= sc < image[0].length 。
image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535] 内。

Submission

运行时间: 19 ms

内存: 16.1 MB

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        oldColor=image[sr][sc]
        if oldColor==newColor:
            return image
        q=deque([[sr,sc]])
        m,n=len(image),len(image[0])
        while q:
            x,y=q.popleft()
            image[x][y]=newColor
            for dx,dy in [[-1,0],[0,-1],[1,0],[0,1]]:
                nx,ny=x+dx,y+dy
                if 0 <= nx <m and 0<=ny<n and image[nx][ny]==oldColor:
                    q.append([nx,ny])
        return image

Explain

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

时间复杂度: O(m*n)

空间复杂度: O(m*n)

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        oldColor = image[sr][sc]  # 获取起始点的原始颜色
        if oldColor == newColor:
            return image  # 如果起始点颜色已经是新颜色，直接返回
        q = deque([[sr, sc]])  # 初始化队列并加入起始点
        m, n = len(image), len(image[0])  # 获取图像的维度
        while q:
            x, y = q.popleft()  # 从队列中取出一个点
            image[x][y] = newColor  # 更改当前点的颜色
            for dx, dy in [[-1, 0], [0, -1], [1, 0], [0, 1]]:  # 检查四个方向
                nx, ny = x + dx, y + dy  # 计算相邻点的坐标
                if 0 <= nx < m and 0 <= ny < n and image[nx][ny] == oldColor:  # 确保在边界内并且颜色符合替换条件
                    q.append([nx, ny])  # 将符合条件的点加入队列
        return image  # 返回修改后的图像

Explore

在BFS实现中，确保不重复加入已检查的像素点是通过立即将点的颜色更改为新颜色来实现的。当一个像素点的颜色被改变后，这个点就不会再次被加入队列中，因为后续的颜色检查（是否与旧颜色相同）将会失败。这种方法同时处理了点的访问记录和颜色修改，简化了逻辑且提高了效率。

在开始BFS之前检查起始点的颜色是否已经是新颜色是必要的，因为如果起始点已经是新颜色，那么没有必要执行任何颜色填充操作。这一步可以避免不必要的操作，如初始化队列、进行颜色检查和修改等。此步骤对所有情况都是必要的，它是优化效率的一种简单且有效的方式。

在BFS过程中，如果碰到已经是新颜色的相邻点，这个点将不会被加入队列中。在检查一个点是否应该加入队列时，会比较该点的颜色与旧颜色是否相同。由于点的颜色已经是新颜色，它不符合加入队列的条件（颜色与旧颜色相同），因此不会进行任何操作。这样确保只有颜色需要被更改的点才会被处理。