TNotes.leetcode

Appearance

0733. 图像渲染【简单】

0733. 图像渲染【简单】 ​

1. 📝 题目描述 ​

有一幅以 m x n 的二维整数数组表示的图画 image，其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数 sr，sc 和 color。你应该从像素 image[sr][sc] 开始对图像进行上色填充。

为了完成上色工作：

  1. 从初始像素开始，将其颜色改为 color。
  2. 对初始坐标的上下左右四个方向上相邻且与初始像素的原始颜色同色的像素点执行相同操作。
  3. 通过检查与初始像素的原始颜色相同的相邻像素并修改其颜色来继续重复此过程。
  4. 当没有其它原始颜色的相邻像素时停止操作。

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

示例 1：

img

输入：
image = [
  [1, 1, 1],
  [1, 1, 0],
  [1, 0, 1]
]
sr = 1
sc = 1
color = 2

输出：
[[2,2,2],[2,2,0],[2,0,1]]

解释：在图像的正中间，坐标 (sr,sc)=(1,1) （即红色像素），在路径上所有符合条件的像素点的颜色都被更改成相同的新颜色（即蓝色像素）。

注意，右下角的像素没有更改为 2，因为它不是在上下左右四个方向上与初始点相连的像素点。

示例 2：

输入：
image = [
  [0, 0, 0],
  [0, 0, 0]
]
sr = 0
sc = 0
color = 0

输出：
[
  [0, 0, 0],
  [0, 0, 0]
]

解释：初始像素已经用 0 着色，这与目标颜色相同。因此，不会对图像进行任何更改。

提示：

  • m == image.length
  • n == image[i].length
  • 1 <= m, n <= 50
  • 0 <= image[i][j], color < 2^16
  • 0 <= sr < m
  • 0 <= sc < n

2. 🎯 s.1 - DFS 递归 ​

js
/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} newColor
 * @return {number[][]}
 */
var floodFill = function (image, sr, sc, newColor) {
  const row_num = image.length // 行数
  const col_num = image[0].length // 列数
  const start_color = image[sr][sc] // 开始颜色

  if (start_color === newColor) return image

  // 递归上色
  const fill = (r, c) => {
    if (r < 0 || r >= row_num || c < 0 || c >= col_num) return // 越界
    if (image[r][c] !== start_color) return // 不是开始颜色

    image[r][c] = newColor // 当前位置
    fill(r - 1, c) // 上
    fill(r + 1, c) // 下
    fill(r, c - 1) // 左
    fill(r, c + 1) // 右
  }

  fill(sr, sc) // 从初始坐标开始上色
  return image
}
  • 时间复杂度：O(m×n)，最坏情况下遍历整张图
  • 空间复杂度：O(m×n)，最坏情况下递归栈深度为连通区域的大小

算法思路：

  • 记录起始像素的原始颜色 start_color，若与 newColor 相同则直接返回
  • 使用 DFS：越界或颜色不匹配直接返回，匹配则染色并向四个方向递归扩展
  • 通过修改像素为新颜色，隐式避免重复访问，无需额外的 visited 数组
  • 从 (sr, sc) 开始递归，最终返回修改后的 image

Discussions