LeetCode 130. 被围绕的区域

约 6 分钟
文章信息 14 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 面试经典 150 题 字节 阿里 微软 百度 网易 小红书 快手 猿辅导
标签
数组 深度优先搜索 广度优先搜索 矩阵 并查集

题目描述

✅ 130. 被围绕的区域

image-20260928215034200

image-20260928215034201

题意分析

把所有被 X 围住的 O 原地改成 X。这里的连通只包括上下左右：一个 O 所在的连通块只要接触矩阵边界，整块都不能翻转；完全不接触边界的连通块才需要翻转。

因此不必逐块判断是否被包围，可以反过来先找出所有与边界连通、必须保留的 O，最后翻转其余 O。

解法：边界 BFS 标记安全区域

核心思路

[!blue]

把四条边上的 O 同时作为 BFS 起点。每找到一个 O，立即把它改成 # 并入队；出队时再检查它的四个相邻位置。# 既表示这个格子可以保留，也表示它已经被发现，不能再次入队。

这样标记的每个格子，都能沿搜索路径走到某个边界 O，所以一定安全。反过来，任何与边界连通的 O，也一定会沿着这条连通路径被 BFS 找到。因此搜索结束时，# 恰好覆盖了全部安全区域，剩下的 O 就是被围绕的区域。

最后扫描矩阵，把剩余 O 改为 X，把 # 恢复为 O。原矩阵承担了访问标记的作用，不需要另建访问数组。

解题步骤

  1. 空矩阵直接返回，取得行数 rows 和列数 cols，建立坐标队列。
  2. 遍历左右边界，再遍历上下边界，统一调用 offer：越界或不是 O 就跳过，否则先标记为 #，再入队。
  3. 队列非空时取出一个格子，对它的上下左右分别调用 offer。已经标记的格子不会重复入队，四角重复扫描以及只有一行、一列的情况也自然适用。
  4. 队列为空说明所有边界可达的 O 都已找到。此时再扫描全图，完成翻转与标记恢复。

代码实现

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }

        int rows = board.length;
        int cols = board[0].length;
        Deque<int[]> queue = new ArrayDeque<>();

        for (int row = 0; row < rows; row++) {
            offer(board, row, 0, queue);
            offer(board, row, cols - 1, queue);
        }

        for (int col = 0; col < cols; col++) {
            offer(board, 0, col, queue);
            offer(board, rows - 1, col, queue);
        }

        while (!queue.isEmpty()) {
            int[] cell = queue.pollFirst();
            int row = cell[0];
            int col = cell[1];

            offer(board, row + 1, col, queue);
            offer(board, row - 1, col, queue);
            offer(board, row, col + 1, queue);
            offer(board, row, col - 1, queue);
        }

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (board[row][col] == 'O') {
                    board[row][col] = 'X';
                } else if (board[row][col] == '#') {
                    board[row][col] = 'O';
                }
            }
        }
    }

    private void offer(char[][] board, int row, int col, Deque<int[]> queue) {
        if (row < 0
                || row >= board.length
                || col < 0
                || col >= board[0].length
                || board[row][col] != 'O') {
            return;
        }

        // 发现时就标记安全且已访问，防止多个方向重复入队。
        board[row][col] = '#';
        queue.offerLast(new int[] {
            row,
            col
        });
    }
}

func solve(board [][]byte) {
    if len(board) == 0 || len(board[0]) == 0 {
        return
    }

    rows, cols := len(board), len(board[0])
    queue := make([][2]int, 0)
    offer := func(row, col int) {
        if row < 0 || row >= rows ||
            col < 0 || col >= cols ||
            board[row][col] != 'O' {
            return
        }

        // 发现时就标记安全且已访问，防止多个方向重复入队。
        board[row][col] = '#'
        queue = append(queue, [2]int{
            row,
            col,
        })
    }

    for row := 0; row < rows; row++ {
        offer(row, 0)
        offer(row, cols-1)
    }
    for col := 0; col < cols; col++ {
        offer(0, col)
        offer(rows-1, col)
    }
    for head := 0; head < len(queue); head++ {
        row, col := queue[head][0], queue[head][1]
        offer(row+1, col)
        offer(row-1, col)
        offer(row, col+1)
        offer(row, col-1)
    }

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if board[row][col] == 'O' {
                board[row][col] = 'X'
            } else if board[row][col] == '#' {
                board[row][col] = 'O'
            }
        }
    }
}

复杂度分析

设矩阵有 m 行、n 列。

  • 时间复杂度：$O(mn)$。每个格子至多入队一次，每次只检查四个方向，最后完整扫描一次矩阵。
  • 空间复杂度：$O(mn)$。队列最坏需要线性于格子总数的空间；原地标记只省去了额外的访问数组。

关键点总结

[!green]

  • 一个连通块是否安全，取决于它是否接触边界，因此可以从边界反向找出全部安全区域。
  • 入队前标记，保证每个 O 只被搜索一次。
  • 搜索结束后，未标记的 O 才能确定需要翻转。

易错点总结

[!yellow]

  • 只保留边界上的 O：与它相连的内部 O 同样安全，必须继续搜索整个连通块。
  • 把对角线也算作连通：题目只允许上下左右四个方向。
  • 出队后才标记：一个格子可能被多个邻居重复加入队列，应在发现时立即标记。
  • 边搜索边翻转或恢复标记：此时连通关系尚未搜索完整，还会破坏访问状态；统一留到 BFS 结束后处理。
  • 恢复后再次翻转：最终扫描用 if ... else if 区分原有 O 和 #，避免同一格被处理两次。

相似题目

题目 难度 关联与区别
200. 岛屿数量 中等 同样网格连通遍历，本题要保留与边界连通的区域，只翻转内部连通块。
1020. 飞地的数量 中等 同样从边界出发排除可逃离区域，原题统计剩余陆地数，本题修改包围区域。
695. 岛屿的最大面积 中等 用洪水填充标记网格连通分量；本题先保护与边界连通的区域，该题统计各分量面积并取最大。
733. 图像渲染 简单 用洪水填充标记网格连通分量；本题先保护与边界连通的区域，该题修改起点所属的同色分量。
1254. 统计封闭岛屿的数目 中等 用洪水填充标记网格连通分量；本题先保护与边界连通的区域，该题排除接触边界的零分量。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/90013297
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！