LeetCode 1034. 边界着色

2025-04-13 HGNULB 约 7 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 1034. 边界着色

题意分析

给一个二维网格，每格是一种颜色。从 (row, col) 出发，四连通且颜色相同的所有格子构成一个连通分量。要求把这个连通分量的边界格染成新颜色 color，其余格子保持不变，返回修改后的网格。

全题的重点是「边界格」的定义：一个属于该连通分量的格子，如果它位于网格的四条边上，或者它的四个方向邻居中存在不属于该连通分量的格子，它就是边界格。注意这里的判据是「邻居不属于本连通分量」，而不是「邻居颜色不同」——虽然在四连通同色的设定下这两句等价，但只要邻居越界也算「不属于」，两种表述就统一了。所以最简洁的判定是：统计上下左右四个方向中，有多少个是「在界内且颜色等于原色」的，个数小于 4 就是边界格。

由此可见这题分成互不相干的两步：先找出连通分量的全部成员，再在成员中筛出边界。前者是标准的连通块遍历；后者只是对每个成员做一次常数级检查。

有一个陷阱藏在「边遍历边染色」里：染色会改变格子的颜色，而遍历和边界判定都依赖「颜色等于原色」这个条件。如果先染了一部分，后面的格子拿改过色的邻居去比较，就会把本来同色的邻居误判成不同色，凭空多出一堆边界，甚至连通分量都遍历不全。所以必须把染色推迟到遍历完全结束之后，先把边界格的坐标收集起来。

约束是 1 ≤ m, n ≤ 50，颜色值在 [1, 1000]，网格极小，$O(mn)$ 的遍历毫无压力，递归深度最坏 2500 层，Java 与 Go 都能承受。

边界情形：整个网格只有一格时，它四面都越界，same = 0 < 4，自然被判为边界并染色；连通分量本身就是单格时同理；新颜色与原颜色相同时，染色是幂等的，不需要特判。

解法：DFS 标记边界

核心思路

从起点做 DFS，只沿着四方向、颜色等于起点原色的格子扩展，即可访问目标连通分量。访问每个格子时检查四个方向：只要某个方向越界，或相邻格颜色不是原色，当前格就是边界格。

关键是把「判定」和「修改」分成两个阶段：DFS 阶段只记录边界坐标，不改 grid；搜索结束后再统一着色。否则先改过的颜色会干扰后续的连通性和边界判断。当新颜色等于原色时，独立的 visited 也仍能可靠去重。

不变量：每次调用 dfs(r, c) 时，(r,c) 已确定属于起点所在的原色连通分量；置为已访问后，每个分量内格子最多进入一次。DFS 返回时，从该格可达的原色格都已访问，其中满足边界定义的格子均已被记录。

正确性：DFS 的扩展条件与「四连通且同色」定义完全一致，所以访问集合恰好是目标连通分量。对其中每个格子逐一检查四边，判据与题目定义等价，因此记录集合恰好是该分量边界。最后只修改记录集合，内部格和分量外格都保持不变。

解题步骤

保存起点颜色 origin，创建 visited 和边界坐标列表。

DFS 进入格子后立即标记已访问，再枚举四个方向。

若邻居越界或颜色不同，将当前格标记为边界；若邻居同色且未访问，继续 DFS。

DFS 完成后，遍历边界列表并写入新颜色。

对 [[1,2,2],[2,3,2]] 从 (0,1) 开始，目标分量是 (0,1)、(0,2)、(1,2)，三格都存在越界边或异色邻居，因此都染为 3；不连通的 (1,0) 即使同为 2 也不修改。

边界样例是 3 x 3 全 1 网格：外围 8 格应染色，中心 (1,1) 四邻均在同一分量中，必须保持 1。它能检验实现是否把「已访问」误当成「不属于分量」。

代码实现

import java.util.ArrayList;
import java.util.List;

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
}

复杂度分析

设目标连通分量大小为 $s$，网格大小为 $m \times n$。

时间复杂度：$O(s)$，每个分量内格子只访问一次并检查 4 个方向；最坏为 $O(mn)$。

空间复杂度：visited 占 $O(mn)$，边界列表和递归栈最坏各占 $O(s)$，总体为 $O(mn)$。

关键点总结

DFS 扩展条件决定连通分量；边界判据决定哪些已访问格需要修改，两者不要混在一起。

判定依赖原网格颜色，因此先收集、后染色，避免状态污染。

visited 只控制是否继续搜索，不能参与「是否为边界」的判断。

越界方向和异色邻居都直接证明当前格是边界；四邻全为原色才是内部格。

易错点总结

搜索时立即染色：[[1,1],[1,1]] 从 (0,0) 染成 2 时，修改后的邻居会污染后续颜色判断。

用新颜色代替 visited：当 color == origin 时无法标记访问状态，会在相邻格之间无限递归。

把访问标记放在递归之后：两个相邻同色格会互相进入，最终栈溢出；必须进入函数即标记。

只检查异色邻居、不检查越界：全同色 2 x 2 网格会漏掉全部边界格。

用 visited 判断邻居是否属于分量：3 x 3 全同色网格的中心可能被误判为边界；成员关系由原色决定，visited 只用于去重。

先访问 grid[nr][nc] 再判越界：单格网格会数组越界，必须利用短路逻辑先检查坐标。

相似题目

题目	难度	考察点
733. 图像渲染	简单	同一个连通块遍历骨架，但要染整块而非只染边界，可以边走边染（需注意新旧色相同的死循环）
200. 岛屿数量	中等	要对全网格反复起点，统计连通块个数，重点在「已访问」如何避免重复计数
695. 岛屿的最大面积	中等	DFS 需要返回子调用的累加值，而非只做标记，练的是递归返回值的设计
463. 岛屿的周长	简单	同样按「异色或越界的邻居方向数」计数，但要累加成周长而非筛选格子
130. 被围绕的区域	中等	反向思维：从网格边缘反向搜索标记「不该改」的格子，再统一修改其余部分
1020. 飞地的数量	中等	与 130 同一套「从边界倒推」的手法，但统计的是剩余格子数量
417. 太平洋大西洋水流问题	中等	两次独立的反向搜索后求交集，扩展条件从「同色」变成「高度不降」
827. 最大人工岛	困难	先给每个连通块编号并记录大小，再枚举翻转点合并相邻块，是连通块预处理的进阶用法