LeetCode 1034. 边界着色

Categories:

题目描述
思路分析
1. 解法一：DFS 标记边界（推荐）
相似题目

题目描述

✅ 1034. 边界着色

思路分析

解法一：DFS 标记边界（推荐）

核心思路：

先 DFS 找到与起点同色的连通块。

对于每个格子，若在边界或邻居存在不同颜色，则为边界格。

最后仅对边界格上色。

复杂度分析：

时间复杂度：O(mn)，其中 m、n 为网格行列数。

空间复杂度：O(mn)，递归栈与标记数组。

import java.util.*;

class Solution {
    private int m;
    private int n;
    private int[][] grid;
    private boolean[][] visited;
    private List<int[]> borders = new ArrayList<>();

    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        this.visited = new boolean[m][n];

        dfs(row, col, grid[row][col]);

        for (int[] cell : borders) {
            grid[cell[0]][cell[1]] = color;
        }
        return grid;
    }

    private void dfs(int r, int c, int origin) {
        visited[r][c] = true;
        int same = 0;
        int[] dr = {1, -1, 0, 0};
        int[] dc = {0, 0, 1, -1};

        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == origin) {
                same++;
                if (!visited[nr][nc]) {
                    dfs(nr, nc, origin);
                }
            }
        }

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

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

    var dfs func(r, c int)
    dfs = func(r, c int) {
        visited[r][c] = true
        same := 0
        dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

        for _, d := range dirs {
            nr, nc := r+d[0], c+d[1]
            if nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == grid[row][col] {
                same++
                if !visited[nr][nc] {
                    dfs(nr, nc)
                }
            }
        }

        if same < 4 {
            borders = append(borders, [2]int{r, c})
        }
    }

    dfs(row, col)

    for _, cell := range borders {
        grid[cell[0]][cell[1]] = color
    }
    return grid
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	DFS
695. 岛屿的最大面积	中等	DFS
733. 图像渲染	简单	DFS
1034. 边界着色	中等	连通块
130. 被围绕的区域	中等	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/38258955