LeetCode 733. 图像渲染

Categories:

题目描述
思路分析
1. 解法一：DFS / BFS（推荐）
相似题目

题目描述

✅ 733. 图像渲染

思路分析

解法一：DFS / BFS（推荐）

核心思路：

记录起点原始颜色，若与新颜色相同直接返回。

从起点 DFS/BFS，向四个方向扩展，只填充同色区域。

将访问到的像素替换为新颜色。

复杂度分析：

时间复杂度：O(m * n)，其中 m、n 表示图像尺寸。

空间复杂度：O(m * n)，递归栈或队列可能覆盖整个图像。

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int oldColor = image[sr][sc];
        if (oldColor == color) {
            return image;
        }

        dfs(image, sr, sc, oldColor, color);
        return image;
    }

    private void dfs(int[][] image, int r, int c, int oldColor, int newColor) {
        if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) {
            return;
        }
        if (image[r][c] != oldColor) {
            return;
        }

        image[r][c] = newColor;

        dfs(image, r + 1, c, oldColor, newColor);
        dfs(image, r - 1, c, oldColor, newColor);
        dfs(image, r, c + 1, oldColor, newColor);
        dfs(image, r, c - 1, oldColor, newColor);
    }
}

func floodFill(image [][]int, sr int, sc int, color int) [][]int {
	oldColor := image[sr][sc]
	if oldColor == color {
		return image
	}

	var dfs func(r, c int)
	dfs = func(r, c int) {
		if r < 0 || r >= len(image) || c < 0 || c >= len(image[0]) {
			return
		}
		if image[r][c] != oldColor {
			return
		}

		image[r][c] = color

		dfs(r+1, c)
		dfs(r-1, c)
		dfs(r, c+1)
		dfs(r, c-1)
	}

	dfs(sr, sc)
	return image
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	DFS/BFS
695. 岛屿的最大面积	中等	DFS/BFS
130. 被围绕的区域	中等	DFS/BFS
417. 太平洋大西洋水流问题	中等	DFS/BFS
994. 腐烂的橘子	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/93876794