LeetCode 733. 图像渲染

2022-07-14 HGNULB 约 5 分钟

文章信息 8 个分类 · 4 个标签

分类

LeetCode CodeTop 简单 未解决 2-5 字节 华为 滴滴

标签

数组 深度优先搜索 广度优先搜索 矩阵

题目描述

✅ 733. 图像渲染

题意分析

从给定起点开始，把与它上下左右连通、且原始颜色相同的所有像素改成新颜色，返回修改后的图像。连通路径上的每个格子都必须具有起点的原颜色，不能跨过其他颜色到达另一片同色区域。

对角线接触不算连通，图中其他同色但不连通的位置保持原样。新颜色与原颜色相同时，本来就不需要修改，可以直接返回。

解法：DFS 原地染色

核心思路

[!blue]

先保存起点的原始颜色 oldColor，整个遍历都使用这个固定值判断是否属于目标区域。深度优先搜索从起点出发，只继续进入界内且颜色仍为 oldColor 的格子，再沿四个方向扩散。

进入一个合格格子后，先把它改成新颜色，再递归访问邻居。由于新旧颜色不同，已经染过的格子不再满足原色条件，新颜色同时充当已访问标记，防止两个相邻格子互相递归而无法结束。

这样不会染到区域外：每一次进入都来自同色区域中的四方向邻居；也不会漏掉区域内的格子，因为从起点可达的每条同色路径都会沿邻居递归被探索。每个合格格子实际染色一次，之后遇到它时立即返回。

新旧颜色相同时，上述标记方式失效，染色后仍满足原色条件，所以要在搜索前直接结束。这里的修改就是最终结果，递归返回时不需要恢复原颜色，与枚举路径的回溯不同。

解题步骤

1. 保存起点原颜色；它已经等于目标颜色时，直接返回原图。
2. 从起点调用 DFS，先排除越界位置，再排除颜色不等于原色的位置。
3. 立即将当前格改成新色，标记它已经处理。
4. 递归访问上、下、左、右邻居，沿同色连通区域继续扩散。
5. 搜索结束后返回原图，此时目标区域已原地修改。

代码实现

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
}

复杂度分析

• 时间复杂度：最坏 $O(mn)$。目标连通区域的每格染色一次，每次最多检查四个邻居；若区域更小，实际处理量与区域大小成正比。
• 空间复杂度：最坏 $O(mn)$，递归路径可能覆盖整片区域。虽然不需要访问数组，调用栈仍占用空间。

关键点总结

[!green]

• 固定比较起点的原颜色，只遍历该颜色的四连通分量。
• 先染色再扩散，新色同时成为访问标记。
• 同色无需搜索，也避免标记无变化引起的循环访问。
• 不恢复颜色，递归完成后的改动就是要返回的结果。

易错点总结

[!yellow]

• 改写起点之后再从起点读取原色，整个搜索的判断基准会被换成新颜色。
• 递归邻居之后才染色，相邻未标记格子会反复调用对方。
• 新旧颜色相同仍然依赖染色标记，无法区分已经访问的位置。
• 允许斜向扩散，或把所有同色像素都改掉，扩大了起点四连通区域的范围。
• 递归返回时恢复原色，会撤销题目需要保留的渲染结果。
• 把原地修改误写成常数辅助空间，漏算可能达到区域大小的递归栈。

相似题目

题目	难度	关联与区别
200. 岛屿数量	中等	同样遍历四连通区域，本题只从一个起点出发并改色，原题统计全部陆地分量。
529. 扫雷游戏	中等	同样点击后扩散，本题所有同色格都可继续，扫雷只在周围无雷时继续展开。
695. 岛屿的最大面积	中等	用洪水填充标记网格连通分量；本题修改起点所属的同色分量，该题统计各分量面积并取最大。
1020. 飞地的数量	中等	用洪水填充标记网格连通分量；本题修改起点所属的同色分量，该题从边界排除可逃离的陆地。
1254. 统计封闭岛屿的数目	中等	用洪水填充标记网格连通分量；本题修改起点所属的同色分量，该题排除接触边界的零分量。

转载与许可

作者 HGNULB

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

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！