LeetCode 1034. 边界着色

约 6 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
数组 深度优先搜索 广度优先搜索 矩阵

题目描述

✅ 1034. 边界着色

image-20260929073551231

image-20260929073551358

题意分析

先找出与给定起点颜色相同、通过上下左右连接到起点的整个连通区域，只将这个区域的边界格改成指定颜色，其内部格保持原色。

一个区域成员只要位于网格外边缘，或四邻中有不同颜色的格子，就属于边界。其他地方即使颜色相同，只要不与起点连通，也不属于本次需要修改的区域。

解法：DFS 标记边界

核心思路

[!blue]

从起点沿原色格做 DFS，就能枚举它所属的连通区域。先保存起点颜色 origin，并用单独的 visited 记录已经搜索过的格子，防止同色邻居之间反复递归。

对每个已经进入的区域成员，检查四个邻居。如果某个方向越过网格，说明这一侧暴露在网格外；如果邻居颜色不同，说明这一侧贴着区域外部。出现任一情况，当前格就是边界。

邻居颜色相同，则它通过当前格与起点相连，一定属于同一区域。它是否已经访问过只决定还要不要递归，不能用来判断是否位于区域外；已访问的同色邻居仍然是内部连接。

搜索时先不修改颜色，只把边界坐标加入列表。否则一个已经改色的邻居可能被后续格子看成异色，使内部格被误判为边界。所有判断都基于原网格完成后，再统一给边界列表染色，就不会混淆原有结构与新颜色。

新颜色即使与原色相同，单独的访问标记也仍然有效，搜索能够正常结束；内部格和其他连通块始终不在修改列表中。

解题步骤

  1. 保存原色，创建访问数组和边界坐标列表，从起点 DFS。
  2. 进入格子立即标记为已访问，初始化当前格的边界标记为假。
  3. 检查四邻：越界或异色就标记当前格为边界；同色且未访问则继续 DFS。
  4. 四个方向检查完后，若当前格为边界，将它加入列表一次。
  5. 完成整个连通区域的搜索后，只修改列表中的坐标，返回原矩阵。

代码实现

class Solution {
    private int[][] grid;
    private boolean[][] visited;
    private List<int[]> borders;
    private int rows;
    private int cols;
    private int origin;
    private static final int[][] DIRS = {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1}
    };

    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        this.grid = grid;
        rows = grid.length;
        cols = grid[0].length;
        origin = grid[row][col];
        visited = new boolean[rows][cols];
        borders = new ArrayList<>();

        dfs(row, col);

        // 边界全部确定后统一改色，搜索期间保持原色不变。
        for (int[] cell : borders) {
            grid[cell[0]][cell[1]] = color;
        }

        return grid;
    }

    private void dfs(int r, int c) {
        // 进入格子就标记，避免相邻同色格反复递归。
        visited[r][c] = true;
        boolean isBorder = false;

        for (int[] dir : DIRS) {
            int nr = r + dir[0];
            int nc = c + dir[1];

            // 越界或异色说明当前格是边界，访问标记不参与边界判定。
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] != origin) {
                isBorder = true;
            } else if (!visited[nr][nc]) {
                dfs(nr, nc);
            }
        }

        if (isBorder) {
            borders.add(new int[] {
                r,
                c
            });
        }
    }
}

func colorBorder(grid [][]int, row int, col int, color int) [][]int {
    m, n := len(grid), len(grid[0])
    origin := grid[row][col]
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    borders := make([][2]int, 0)
    dirs := [4][2]int{
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1},
    }

    var dfs func(r, c int)
    dfs = func(r, c int) {
        // 进入格子就标记，避免相邻同色格反复递归。
        visited[r][c] = true
        isBorder := false

        for _, d := range dirs {
            nr, nc := r+d[0], c+d[1]
            // 越界或异色说明当前格是边界，访问标记不参与边界判定。
            if nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] != origin {
                isBorder = true
            } else if !visited[nr][nc] {
                dfs(nr, nc)
            }
        }

        if isBorder {
            borders = append(borders, [2]int{
                r,
                c,
            })
        }
    }

    dfs(row, col)

    // 边界全部确定后统一改色，搜索期间保持原色不变。
    for _, cell := range borders {
        grid[cell[0]][cell[1]] = color
    }
    return grid
}

复杂度分析

  • 时间复杂度：$O(mn)$，初始化 visited 需要遍历网格；若连通区域有 s 格，实际搜索和染色为 $O(s)$。
  • 空间复杂度：$O(mn)$，访问数组占 $O(mn)$，递归栈和边界列表最坏各占 $O(s)$。

关键点总结

[!green]

  • 连通范围由原色和四方向连接决定，访问标记只用于去重。
  • 越界和异色邻居都代表暴露边，任一暴露边就足以让当前格成为边界。
  • 先判断全部边界、再统一修改，保证后续检查不受已染色格子的影响。

易错点总结

[!yellow]

  • 只判断邻居异色而不判断越界，会漏掉全同色区域贴着网格外侧的边界。
  • 将所有同色格都染色，会修改区域内部，甚至影响未与起点连接的其他区域。
  • 把已经访问过的邻居当作区域外，会错误地把内部格识别为边界。
  • 搜索过程中直接使用新色覆盖原网格，会影响后面格子的同色和边界判断。
  • 用染色替代访问标记，新色与原色相同时无法阻止重复搜索。
  • 在检查坐标合法前访问邻居数组，会在外边缘越界。

相似题目

题目 难度 关联与区别
733. 图像渲染 简单 先识别与起点同色的连通分量，本题只修改边界格，普通渲染修改整块。
463. 岛屿的周长 简单 同样识别暴露在分量外的边，原题按边计周长，本题按边界格染色。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/38258955
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！