图像渲染

难度: Easy

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。

你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行上色填充。

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

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

示例 1:

输入: 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，因为它不是在上下左右四个方向上与初始点相连的像素点。

示例 2:

输入: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
输出: [[2,2,2],[2,2,2]]

提示:

m == image.length
n == image[i].length
1 <= m, n <= 50
0 <= image[i][j], newColor < 2¹⁶
0 <= sr < m
0 <= sc < n

Submission

运行时间: 19 ms

内存: 16.2 MB

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        directions = [[0,1],[1,0],[0,-1],[-1,0]]
        changed_color = image[sr][sc]
        if color == changed_color:
            return image
        stack = [(sr,sc)]
        while(stack):
            curr = stack.pop()
            row,col = curr[0],curr[1]
            image[row][col] = color
            for d in directions:
                newrow, newcol = d[0] + row, d[1] + col
                if newrow in range(len(image)) and newcol in range(len(image[newrow])) and image[newrow][newcol] == changed_color:
                    stack.append((newrow,newcol))
        return image

Explain

该题解使用深度优先搜索（DFS）的思路，具体步骤如下： 1. 定义方向数组 directions，表示上下左右四个方向。 2. 记录初始点的颜色为 changed_color。 3. 如果初始点的颜色与新颜色相同，直接返回原图像。 4. 将初始点坐标压入栈 stack 中。 5. 当栈不为空时，循环执行以下操作： - 弹出栈顶元素 curr，获取当前点的坐标 (row, col)。 - 将当前点的颜色更改为新颜色。 - 遍历四个方向： - 计算新坐标 (newrow, newcol)。 - 如果新坐标在图像范围内且颜色与初始点相同，将新坐标压入栈中。 6. 返回更改后的图像。

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

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

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        directions = [[0,1],[1,0],[0,-1],[-1,0]]  # 定义方向数组
        changed_color = image[sr][sc]  # 记录初始点的颜色
        if color == changed_color:  # 如果初始点颜色与新颜色相同，直接返回原图像
            return image
        stack = [(sr,sc)]  # 将初始点坐标压入栈中
        while(stack):  # 当栈不为空时，循环执行以下操作
            curr = stack.pop()  # 弹出栈顶元素
            row,col = curr[0],curr[1]  # 获取当前点的坐标
            image[row][col] = color  # 将当前点的颜色更改为新颜色
            for d in directions:  # 遍历四个方向
                newrow, newcol = d[0] + row, d[1] + col  # 计算新坐标
                if newrow in range(len(image)) and newcol in range(len(image[newrow])) and image[newrow][newcol] == changed_color:  # 如果新坐标在图像范围内且颜色与初始点相同
                    stack.append((newrow,newcol))  # 将新坐标压入栈中
        return image  # 返回更改后的图像

Explore

深度优先搜索（DFS）和广度优先搜索（BFS）都可以用来解决图像渲染问题，但DFS在实现上通常更简洁。在DFS中使用栈来存储待处理的节点，而在BFS中则需要使用队列。在某些情况下，DFS的递归或栈的使用可以更快地到达远端节点，尤其是在需要涂色的区域较大或者形状复杂时。此外，DFS的空间复杂度在最坏情况下与BFS相同，都是O(n)，但在平均情况下，DFS因为早日达到深层节点而可能使用更少的空间。因此，选择DFS还是BFS更多基于实现的偏好和特定问题的性质。

在提供的代码中，每次遍历新的方向都会独立检查新坐标是否在图像的有效范围内，这个过程中确实存在重复计算。例如，对于每一个方向，都会重新计算 `newrow in range(len(image))` 和 `newcol in range(len(image[newrow]))`，这些操作可以优化。一种方法是先计算图像的行数和列数，将其存储为常量，然后直接使用这些常量来检查坐标的有效性，从而避免在每次迭代中重新计算图像的维度。

在这个DFS实现中，栈用于存储每个需要处理的像素点。只有栈为空时，算法才会结束，这是因为栈为空意味着没有更多的相邻像素需要变色。这种处理确保了所有与初始点颜色相同且相邻的像素都被遍历并着色。如果提前退出循环，可能会导致某些应该被着色的区域未被处理，从而得到错误的结果。因此，持续处理直到栈为空是确保正确性的必需步骤。

直接修改输入的`image`数组可以节省空间和时间，因为不需要创建和维护一个额外的数组副本。然而，这种做法可能不安全或不可取，特别是在需要保持原始数据不变的情况下。如果不希望修改原始输入，可以先复制一份`image`数组，然后在这个副本上进行操作。这样做虽然增加了空间复杂度，但保证了原始数据的安全性。