LeetCode 733. 图像渲染

字数 2356 2025-10-26 09:00:52

LeetCode 733. 图像渲染

题目描述

有一幅以二维整数网格表示的图画，image。每一个整数 image[i][j] 表示该像素的灰度值。给你三个整数：sr（行），sc（列）和 newColor（新颜色）。你需要从像素 image[sr][sc] 开始，对图像进行“上色”（也称为“洪水填充”）。

“洪水填充”的意思是，从初始像素点开始，把所有与初始点颜色相同且相邻（上下左右四个方向）的像素点，以及这些点的相邻点（同样要求颜色相同且相邻），都更改为新的颜色。最终，你需要返回修改后的图像。

解题过程

这个问题的核心是遍历所有与起点颜色相同且连通的区域。我们可以使用深度优先搜索（DFS） 或广度优先搜索（BFS） 算法来解决。它们的思想都是从起点出发，系统地探索所有可达的、颜色相同的像素点。

我们将使用深度优先搜索（DFS） 来详细讲解，因为它更容易实现，思路也更直观。

第一步：分析基本情况

在开始搜索之前，我们需要考虑一个特殊情况：

如果起点 (sr, sc) 的颜色 originalColor 已经等于 newColor，那么我们不需要做任何修改，直接返回原图像即可。因为如果进行填充，会导致算法在相同的颜色区域里无限循环（比如，把一个白色区域填充成白色，程序会不断访问已经填充过的点）。

第二步：定义DFS递归函数

我们将编写一个递归函数 dfs(x, y)，它的作用是将坐标 (x, y) 的颜色填充为 newColor，并继续向它的四个邻居方向进行同样的操作。

改变当前点颜色：进入函数后，首先将当前像素 image[x][y] 的颜色设置为 newColor。
定义四个探索方向：我们需要定义四个移动方向：上、右、下、左。通常用一个二维数组表示：directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]。每个元素 (dx, dy) 代表在x轴和y轴上的移动增量。
探索四个方向的邻居：
- 对于每一个方向 (dx, dy)，计算邻居的坐标：newX = x + dx，newY = y + dy。
- 检查邻居坐标的有效性：确保新坐标 (newX, newY) 没有超出图像的边界（即 0 <= newX < 图像行数 且 0 <= newY < 图像列数）。
- 检查邻居颜色：如果邻居坐标有效，并且它的颜色等于我们最初记录的 originalColor（即起点最初的颜色），那么说明这个邻居是需要被填充的连通区域的一部分。
递归调用：对于满足上述条件的邻居，我们递归地调用 dfs(newX, newY)。

第三步：算法流程

获取图像的行数 m 和列数 n。
记录起点 (sr, sc) 的原始颜色 originalColor = image[sr][sc]。
检查特殊情况：如果 originalColor == newColor，直接返回 image。
调用递归函数 dfs(sr, sc)。
返回修改后的 image。

举例说明

假设我们有如下图像，起点是 (1, 1)（中心点，颜色为1），新颜色是2。

原始图像：
[
  [1, 1, 1],
  [1, 1, 0],
  [1, 0, 1]
]

originalColor = 1，newColor = 2，两者不同，继续。
从 (1, 1) 开始，将其颜色从1改为2。
探索 (1, 1) 的四个方向：
- 上 (1-1, 1) = (0, 1)：颜色为1，等于 originalColor，递归进入 (0, 1)。
- 右 (1, 1+1) = (1, 2)：颜色为0，不等于 originalColor，忽略。
- 下 (1+1, 1) = (2, 1)：颜色为0，不等于 originalColor，忽略。
- 左 (1, 1-1) = (1, 0)：颜色为1，等于 originalColor，递归进入 (1, 0)。
处理 (0, 1)：
- 将其颜色改为2。
- 探索其四个方向：
  - 上 (-1, 1)：越界，忽略。
  - 右 (0, 2)：颜色为1，递归进入 (0, 2)。
  - 下 (1, 1)：颜色已变为2（不等于 originalColor），忽略。
  - 左 (0, 0)：颜色为1，递归进入 (0, 0)。
处理 (1, 0)：
- 将其颜色改为2。
- 探索其四个方向：
  - 上 (0, 0)：颜色为1，但此时 (0, 0) 还没有被处理（它会在第4步的左方向被处理），但颜色仍是1，所以会再次递归进入 (0, 0)。（这里体现了DFS的深入特性，它先沿着一个方向走到底）。
这个过程会继续下去，直到所有颜色为1且与 (1, 1) 连通的点都被访问并修改。最终结果是中心区域和左上角的“1”被填充为“2”，而右下角的“1”因为被“0”隔开，所以不会被填充。

结果图像：
[
  [2, 2, 2],
  [2, 2, 0],
  [2, 0, 1]
]

关键点总结

核心思想：使用DFS或BFS遍历连通区域。
终止条件：隐含在递归的边界检查中（坐标越界或颜色不匹配则返回）。
避免循环：通过先将当前点颜色改为 newColor，使得后续搜索遇到该点时因其颜色不等于 originalColor 而不会再次处理它。同时，第一步的特殊情况检查也是防止无限循环的关键。
时间复杂度：O(m × n)，最坏情况下需要遍历整个图像。m和n分别是图像的行数和列数。
空间复杂度：O(m × n)，主要为递归调用栈的深度，最坏情况下（比如整个图像都是同一种颜色）深度可能达到 m×n。如果使用BFS（队列实现），空间复杂度也是 O(m × n)。

LeetCode 733. 图像渲染题目描述有一幅以二维整数网格表示的图画， image 。每一个整数 image[i][j] 表示该像素的灰度值。给你三个整数： sr （行）， sc （列）和 newColor （新颜色）。你需要从像素 image[sr][sc] 开始，对图像进行“上色”（也称为“洪水填充”）。 “洪水填充”的意思是，从初始像素点开始，把所有与初始点颜色相同且相邻（上下左右四个方向）的像素点，以及这些点的相邻点（同样要求颜色相同且相邻），都更改为新的颜色。最终，你需要返回修改后的图像。解题过程这个问题的核心是遍历所有与起点颜色相同且连通的区域。我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来解决。它们的思想都是从起点出发，系统地探索所有可达的、颜色相同的像素点。我们将使用深度优先搜索（DFS）来详细讲解，因为它更容易实现，思路也更直观。第一步：分析基本情况在开始搜索之前，我们需要考虑一个特殊情况：如果起点 (sr, sc) 的颜色 originalColor 已经等于 newColor ，那么我们不需要做任何修改，直接返回原图像即可。因为如果进行填充，会导致算法在相同的颜色区域里无限循环（比如，把一个白色区域填充成白色，程序会不断访问已经填充过的点）。第二步：定义DFS递归函数我们将编写一个递归函数 dfs(x, y) ，它的作用是将坐标 (x, y) 的颜色填充为 newColor ，并继续向它的四个邻居方向进行同样的操作。改变当前点颜色：进入函数后，首先将当前像素 image[x][y] 的颜色设置为 newColor 。定义四个探索方向：我们需要定义四个移动方向：上、右、下、左。通常用一个二维数组表示： directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] 。每个元素 (dx, dy) 代表在x轴和y轴上的移动增量。探索四个方向的邻居：对于每一个方向 (dx, dy) ，计算邻居的坐标： newX = x + dx ， newY = y + dy 。检查邻居坐标的有效性：确保新坐标 (newX, newY) 没有超出图像的边界（即 0 <= newX < 图像行数且 0 <= newY < 图像列数）。检查邻居颜色：如果邻居坐标有效，并且它的颜色等于我们最初记录的 originalColor （即起点最初的颜色），那么说明这个邻居是需要被填充的连通区域的一部分。递归调用：对于满足上述条件的邻居，我们递归地调用 dfs(newX, newY) 。第三步：算法流程获取图像的行数 m 和列数 n 。记录起点 (sr, sc) 的原始颜色 originalColor = image[sr][sc] 。检查特殊情况：如果 originalColor == newColor ，直接返回 image 。调用递归函数 dfs(sr, sc) 。返回修改后的 image 。举例说明假设我们有如下图像，起点是 (1, 1) （中心点，颜色为1），新颜色是2。 originalColor = 1 ， newColor = 2 ，两者不同，继续。从 (1, 1) 开始，将其颜色从1改为2。探索 (1, 1) 的四个方向：上 (1-1, 1) = (0, 1) ：颜色为1，等于 originalColor ，递归进入 (0, 1) 。右 (1, 1+1) = (1, 2) ：颜色为0，不等于 originalColor ，忽略。下 (1+1, 1) = (2, 1) ：颜色为0，不等于 originalColor ，忽略。左 (1, 1-1) = (1, 0) ：颜色为1，等于 originalColor ，递归进入 (1, 0) 。处理 (0, 1) ：将其颜色改为2。探索其四个方向：上 (-1, 1) ：越界，忽略。右 (0, 2) ：颜色为1，递归进入 (0, 2) 。下 (1, 1) ：颜色已变为2（不等于 originalColor ），忽略。左 (0, 0) ：颜色为1，递归进入 (0, 0) 。处理 (1, 0) ：将其颜色改为2。探索其四个方向：上 (0, 0) ：颜色为1，但此时 (0, 0) 还没有被处理（它会在第4步的左方向被处理），但颜色仍是1，所以会再次递归进入 (0, 0) 。（这里体现了DFS的深入特性，它先沿着一个方向走到底）。这个过程会继续下去，直到所有颜色为1且与 (1, 1) 连通的点都被访问并修改。最终结果是中心区域和左上角的“1”被填充为“2”，而右下角的“1”因为被“0”隔开，所以不会被填充。关键点总结核心思想：使用DFS或BFS遍历连通区域。终止条件：隐含在递归的边界检查中（坐标越界或颜色不匹配则返回）。避免循环：通过先将当前点颜色改为 newColor ，使得后续搜索遇到该点时因其颜色不等于 originalColor 而不会再次处理它。同时，第一步的特殊情况检查也是防止无限循环的关键。时间复杂度：O(m × n)，最坏情况下需要遍历整个图像。m和n分别是图像的行数和列数。空间复杂度：O(m × n)，主要为递归调用栈的深度，最坏情况下（比如整个图像都是同一种颜色）深度可能达到 m×n。如果使用BFS（队列实现），空间复杂度也是 O(m × n)。