LeetCode 733. 图像渲染

2022-07-14 HGNULB 约 9 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

✅ 733. 图像渲染

题意分析

给一张用二维数组表示的图片、一个起始像素 (sr, sc) 和一个新颜色，要求把「从起点出发、只经过上下左右四个方向、且沿途颜色都与起点原始颜色相同」的那一整片区域全部换成新颜色，最后返回整张图。

有三个限定词必须同时满足才染色：与起点四方向连通、颜色等于起点的原始颜色。只要有一个不满足就不能碰。特别注意是「起点的原始颜色」而不是「相邻格子的颜色」——一旦起点被改写，这个基准就没了，所以必须提前存下来。

网格规模是行列各不超过 50，颜色取值 0 到 2^16，规模很小，暴力遍历整片区域完全够用。

题目要求返回修改后的图片，而入参本身就是可变的二维数组，所以原地修改是被允许的，这为「用染色本身充当访问标记」留下了空间。

最容易被忽略的边界是：新颜色可能恰好等于起点的原始颜色。此时整张图本来就不需要任何改动，但如果照常递归，格子改完颜色还是等于基准色，会被反复当成「未处理」而无限递归下去。

其它边界还有：起点周围全是别的颜色（只染起点一格）、整张图同色（全部染色）、以及只有一行或一列的网格。

解法：DFS 原地染色

核心思路

直接的想法是把这片连通区域当成一个待展开的集合：从起点开始，不断把「颜色等于基准色且与已收集格子相邻」的格子加进来，直到收不动为止，最后统一改色。这个思路是对的，但如果每轮都重新扫全图找可扩展的格子，代价会是区域大小乘以图的面积。

瓶颈在于「找下一个该处理的格子」。其实不必满图去找——每个格子的候选邻居只有固定的四个，从当前格子直接往四个方向递归即可，扩展是就地发生的。

接下来的关键问题是如何避免重复访问：两个相邻格子会互相递归，不加控制就会来回死循环。常规做法是另开一个同样大小的 visited 数组，但这里有个更省的观察——染色本身就是访问标记。一个格子一旦被改成新颜色，它就不再等于基准色，后续任何递归到它的调用都会在「颜色不匹配」这一关被挡回去。

于是递归函数维持的不变量是：每次调用返回后，以该格子为起点、颜色仍为基准色的连通区域已经全部被染成新色；而且任何一个格子最多被真正处理一次（第二次到达时颜色已变）。

这个「用结果当标记」的技巧成立有一个前提：新颜色必须与基准色不同。若两者相同，染色不会改变任何格子的颜色，标记功能失效，递归就再也停不下来。所以必须在最开头加一句判断，相同则直接返回原图。

递归出口只有两条：下标越界，或当前颜色不等于基准色。把出口写在函数入口处（而不是在递归前逐个检查邻居），四个方向的递归就能整齐地写成四行，不必为每个方向重复写边界判断。

解题步骤

先读出 oldColor = image[sr][sc] 存进变量。这一步必须在任何修改之前完成，因为整个过程的判定基准是起点的原始颜色，改完就取不到了。

紧接着判断 oldColor == color，成立就直接返回原图。理由是此时染色无法改变格子颜色，无法充当访问标记，递归会在相邻格子之间无限来回。

从 (sr, sc) 发起递归。递归函数只接收当前坐标和两个颜色，不需要额外的访问数组。

递归函数入口先判越界：行下标小于 0 或不小于行数、列下标小于 0 或不小于列数，任一成立就返回。把判断放在入口而不是调用前，四个方向就能无差别地递归。

再判 image[r][c] != oldColor 就返回。这一条同时承担了两个职责：挡住颜色本来就不同的格子（不属于目标区域），以及挡住已经染过色的格子（防止重复访问）。

通过两道关卡后，先把当前格子染成新颜色，再向上下左右四个方向递归。染色必须在递归之前完成，否则四个方向会在当前格子仍是基准色时互相递归回来，形成环。

全部递归结束后返回 image。图是原地改的，返回的还是同一个数组对象。

**以 image = [[1,1,1],[1,1,0],[1,0,1]]

、sr = 1

、sc = 1

、color = 2

走一遍**：oldColor = image[1][1] = 1，与 2 不同，继续。进入 (1,1)，颜色是 1，染成 2，图变为 [[1,1,1],[1,2,0],[1,0,1]]。先向下走 (2,1)，那里是 0 不等于 1，立即返回。再向上走 (0,1)，是 1，染成 2；从 (0,1) 出发：向下回到 (1,1) 此时已是 2，返回；向上越界返回；向右到 (0,2) 是 1，染成 2，它的四个方向分别是 (1,2) 的 0、越界、越界和已染色的 (0,1)，全部返回；向左到 (0,0) 是 1，染成 2，从它向下到 (1,0) 是 1，染成 2，再向下到 (2,0) 是 1，染成 2，(2,0) 的四邻是越界、已染的 (1,0)、值为 0 的 (2,1) 和越界，全部返回；回到 (1,0) 后其余方向都已染色或越界；回到 (0,0) 同理。递归回到 (1,1)，剩下向右的 (1,2) 是 0、向左的 (1,0) 已是 2，都返回。最终图为 [[2,2,2],[2,2,0],[2,0,1]]，与样例一致：右下角那个 1 因为被 0 隔断、与起点不连通，保持原样。

代码实现

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(m \cdot n)$，其中 m、n 为网格的行数与列数；每个格子最多被真正处理一次（第二次到达时颜色已变，立即返回），每次处理只发起四个常数级调用。

空间复杂度：$O(m \cdot n)$，来自递归调用栈；整张图同色时递归会沿着一条蛇形路径深入到全部格子，这也是 50 × 50 这个规模能放心用递归的原因。

关键点总结

网格连通块类问题的骨架是固定的：入口判越界、判是否属于目标、打标记、向四个方向递归。把两条出口都放在函数入口，调用处就不必为每个方向重复写判断。

「用结果本身充当访问标记」能省掉一个同规模的 visited 数组，但要先确认这个标记确实是不可逆的；本题里它的成立前提就是新旧颜色不同，这也正是那句提前返回存在的理由。

修改状态必须发生在递归之前。先改后递归，邻居回头访问时才会被挡住；顺序反过来就会形成环。

判定基准（这里是起点原始颜色）如果会被过程本身破坏，就必须在动手前先存一份，这类「先快照再修改」的习惯在原地算法里非常通用。

面试视角：写完 DFS 后要能主动说出递归深度最坏是 $O(mn)$，并给出 BFS 版本作为栈溢出的替代方案；被追问「怎么改成八方向」「怎么统计区域面积」时，只需在同一骨架上改方向数组或加返回值，这说明你抓的是模板而不是这一道题。

易错点总结

错误写法：漏掉 oldColor == color 的提前返回 → image = [[0,0,0],[0,0,0]]、sr = 0、sc = 0、color = 0 时，染色不改变任何值，相邻两格互相递归，直接栈溢出。

错误写法：把基准色写成 image[r][c] 在递归函数里现取 → 每层用的基准都变成当前格子自己的颜色，判断恒成立，会把整张图不分区域地染满。

错误写法：先递归四个方向、最后才给当前格子染色 → 当前格子在整个递归期间仍是基准色，邻居会立刻递归回来，形成无限互相调用。

错误写法：在四个方向的调用处逐个写越界判断，却漏掉其中一个 → image 只有一行时向上或向下的那次调用会用负下标或越界下标访问，抛出下标异常；把判断收进函数入口只需写一次。

错误写法：越界判断写成 r > image.length 或 c > image[0].length → 少了等号，下标恰好等于长度时仍然放行，越界一格。

错误写法：仿照回溯模板，在四个方向递归结束后把格子改回 oldColor「恢复现场」 → 这题求的是最终状态而不是路径，恢复现场会把已完成的染色全部抹掉，同时标记也失效，重新陷入死循环。

错误写法：另开 visited 数组却只在染色分支里标记，忘了颜色不匹配的格子也算访问过 → 逻辑虽然仍正确，但同一批不匹配的格子会被反复访问，退化成对每个格子做常数次以上的重复判断；本题直接用颜色当标记就没有这个问题。

错误写法：把新颜色写进一份复制出来的图，判断时却读原图 → 已染色的格子在原图里仍是基准色，无法起到标记作用，递归照样停不下来。

相似题目

题目	难度	考察点
200. 岛屿数量	中等	要在全图起点上循环，统计连通块个数
130. 被围绕的区域	中等	反向从边界出发染色，再统一回填
695. 岛屿的最大面积	中等	递归需要返回值来累加区域面积
1020. 飞地的数量	中等	先排除与边界相连的部分，再数剩余格子
417. 太平洋大西洋水流问题	中等	从两组边界分别逆流搜索并取交集
827. 最大人工岛	困难	先给连通块编号再枚举翻转一个 0 的收益
面试题 08.10. 颜色填充	简单	与本题同题，可用来默写四方向骨架