LeetCode 面试题 08.10. 颜色填充

约 5 分钟
文章信息 3 个分类 4 个标签
分类
LeetCode 简单 程序员面试金典（第 6 版）
标签
数组 深度优先搜索 广度优先搜索 矩阵

题目描述

✅ 面试题 08.10. 颜色填充

image-20260929011223387

题意分析

把起点所在的同色四连通区域全部改为新颜色。区域内的格子必须能沿上、下、左、右相邻路径到达起点，并且原颜色与起点相同；仅仅颜色相同但不连通的格子不改变。

解法：从起点扩散并用新颜色标记

核心思路

[!blue]

先保存起点的原颜色 oc，此后所有进入条件都与这个固定颜色比较。DFS 从起点出发，越界或颜色不同就停止；符合条件的格子先改为新颜色，再递归检查它的四个邻居。

当新旧颜色不同时，改色同时起到访问标记的作用：再次从邻居走回这个格子时，它已经不等于 oc，会立即返回。因此无需额外的访问数组，但必须在递归邻居之前改色，才能阻断相邻格子之间的来回访问。

新颜色恰好等于原颜色时，写回同样的值无法表示“已访问”。代码额外检查当前格是否已经等于新颜色，使初始 DFS 直接返回；图像本来就是期望颜色，不需要继续扩散。

DFS 只沿原色格子的四邻边扩展，所以不会离开起点的同色区域；对区域内任一格，沿着它到起点的原色路径逐步扩展又一定能到达它。每个格子只在第一次进入时展开邻居，因而整个区域恰好被填充，其他位置保持不变。

解题步骤

  1. 在任何写入前，保存起点原颜色和目标新颜色。
  2. 从起点调用 DFS，先判断坐标范围，再读取颜色判断是否可以进入。
  3. 当前颜色不等于原色，或已经等于新色时直接返回。
  4. 将当前格改为新色，再递归四个相邻位置。
  5. 搜索结束后返回原图像数组，修改已经在数组中完成。

方向数组 [-1, 0, 1, 0, -1] 每两个相邻值组成一个行列偏移，依次表示上、右、下、左，不包含对角方向。

代码实现

class Solution {
    private int[] dirs = {
        -1,
        0,
        1,
        0,
        -1
    };
    private int[][] image;
    private int nc;
    private int oc;

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        nc = newColor;
        // 必须在任何写入之前取出起点原色。
        oc = image[sr][sc];
        this.image = image;
        dfs(sr, sc);

        return image;
    }

    private void dfs(int i, int j) {
        // image[i][j] == nc 专门用于新旧同色时阻断无限递归。
        if (i < 0
                || i >= image.length
                || j < 0
                || j >= image[0].length
                || image[i][j] != oc
                || image[i][j] == nc) {
            return;
        }

        image[i][j] = nc;

        for (int k = 0; k < 4; ++k) {
            dfs(i + dirs[k], j + dirs[k + 1]);
        }
    }
}

func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
    // 必须在任何写入之前取出起点原色。
    oc := image[sr][sc]
    m, n := len(image), len(image[0])
    dirs := []int{
        -1,
        0,
        1,
        0,
        -1,
    }
    var dfs func(i, j int)
    dfs = func(i, j int) {
        // image[i][j] == newColor 专门用于新旧同色时阻断无限递归。
        if i < 0 || i >= m || j < 0 || j >= n || image[i][j] != oc || image[i][j] == newColor {
            return
        }
        image[i][j] = newColor
        for k := 0; k < 4; k++ {
            dfs(i+dirs[k], j+dirs[k+1])
        }
    }
    dfs(sr, sc)
    return image
}

复杂度分析

  • 时间复杂度：最坏为 $O(mn)$，其中 $m$、$n$ 是图像行列数。每个被填充格子只展开一次，每次检查四个邻居。
  • 空间复杂度：最坏为 $O(mn)$，连通区域可能让递归路径经过所有格子；改色标记本身不需要额外访问数组。

关键点总结

[!green]

  • 始终用起点最初的颜色判断是否属于目标区域，不能在改色后重新取原色。
  • 新旧颜色不同时，改色就是访问标记；同色时必须直接停止。
  • 先改色再扩散，使每个合法格子只展开一次。

易错点总结

[!yellow]

  • 在检查坐标之前读取数组，越界邻居会触发非法访问。
  • 先递归邻居再改色，可能让尚未标记的相邻格子互相递归。
  • 忽略新旧颜色相同的情况，会失去改色标记的阻断作用。
  • 不能把对角相邻算作连通，也不能仅凭颜色相同就修改图中所有格子。

相似题目

题目 难度 关联与区别
200. 岛屿数量 中等 同样遍历四连通分量并标记访问，原题要统计全部岛屿，本题只从一个起点扩散。
695. 岛屿的最大面积 中等 同样对一个连通区域做 DFS，原题累计面积，本题写入新颜色。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/55070161
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！