733. 图像渲染

🟢 🔖 深度优先搜索 广度优先搜索 数组 矩阵 🔗 力扣open in new window LeetCodeopen in new window

题目

You are given an image represented by an m x n grid of integers image, where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color. Your task is to perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill :

Begin with the starting pixel and change its color to color.
Perform the same process for each pixel that is directly adjacent (pixels that share a side with the original pixel, either horizontally or vertically) and shares the same color as the starting pixel.
Keep repeating this process by checking neighboring pixels of the updated pixels and modifying their color if it matches the original color of the starting pixel.
The process stops when there are no more adjacent pixels of the original color to update.

Return the modified image after performing the flood fill.

Example 1:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2

Output: [[2,2,2],[2,2,0],[2,0,1]]

Explanation:

From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.

Note the bottom corner is not colored 2, because it is not horizontally or vertically connected to the starting pixel.

Example 2:

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0

Output: [[0,0,0],[0,0,0]]

Explanation:

The starting pixel is already colored with 0, which is the same as the target color. Therefore, no changes are made to the image.

Constraints:

m == image.length
n == image[i].length
1 <= m, n <= 50
0 <= image[i][j], color < 216
0 <= sr < m
0 <= sc < n

题目大意

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

为了完成 上色工作 ：

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

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

示例 1:

输入： 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 < 216
0 <= sr < m
0 <= sc < n

解题思路

如果起点 (sr, sc) 的颜色已经等于目标颜色 color，直接返回原始图像即可，避免无限递归。
定义一个方向数组 dirc 表示四连通的上下左右移动。
初始化递归函数 dfs(r, c)：
- 从起点开始，将当前像素染为目标颜色。
- 遍历当前像素的四个方向（上下左右）。
  - 如果某个方向的像素在图像的边界范围内，且颜色与原始起点颜色相同则递归处理。
调用 dfs(sr, sc) 开始深度优先搜索（DFS），将与起点颜色相同的连通区域全部染色。
返回更新后的图像。

复杂度分析

时间复杂度：O(m * n)，最坏情况下，所有像素都被访问一次。
空间复杂度：O(m * n)，DFS 使用的递归栈深度为连通分量的大小，最坏情况下为O(m * n)。

代码

/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} color
 * @return {number[][]}
 */
var floodFill = function (image, sr, sc, color) {
	// 获取图像的行数和列数
	const m = image.length,
		n = image[0].length;

	// 定义上下左右四个方向
	const dirc = [
		[1, 0],
		[-1, 0],
		[0, 1],
		[0, -1]
	];
	const originColor = image[sr][sc]; // 起点颜色

	const dfs = (r, c) => {
		// 将当前像素染成目标颜色
		image[r][c] = color;

		// 遍历四个方向
		for (let [dr, dc] of dirc) {
			// 计算相邻像素的坐标
			const nr = r + dr;
			const nc = c + dc;
			// 对满足条件的像素递归
			if (
				nr >= 0 &&
				nr < m &&
				nc >= 0 &&
				nc < n &&
				image[nr][nc] == originColor
			) {
				dfs(nr, nc);
			}
		}
	};

	// 如果目标颜色和起点颜色相同，无需执行染色
	if (originColor !== color) {
		dfs(sr, sc); // 从起点开始递归搜索
	}

	return image; // 返回更新后的图像
};

733. 图像渲染

# 733. 图像渲染

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

733. 图像渲染

题目

题目大意

解题思路

复杂度分析

代码

相关题目