LeetCode 130. 被围绕的区域

Categories:

题目描述
思路分析
1. 解法一：DFS 反向标记（推荐）
2. 解法二：BFS 反向标记
相似题目

题目描述

✅ 130. 被围绕的区域

思路分析

解法一：DFS 反向标记（推荐）

核心思路：

被围绕的 ‘O’ 一定不与边界相连，因此从四条边上的 ‘O’ 出发做 DFS/BFS，将所有与边界连通的 ‘O’ 标记为临时字符 ‘#’。

遍历完成后，矩阵中剩余的 ‘O’ 均为被围绕的区域，将其翻转为 ‘X’。

最后将 ‘#’ 恢复为 ‘O’，完成整个替换过程。

步骤：

遍历矩阵的四条边，对每个值为 ‘O’ 的格子执行 DFS。

DFS 过程中将连通的 ‘O’ 全部标记为 ‘#’（表示不可翻转）。

再次遍历整个矩阵：’O’ 改为 ‘X’，’#’ 改回 ‘O’，’X’ 保持不变。

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别为矩阵的行数和列数，每个格子最多被访问一次。

空间复杂度：O(m × n)，递归栈深度最坏情况下为矩阵大小。

class Solution {

    private int m;
    private int n;
    private char[][] board;

    public void solve(char[][] board) {
        this.board = board;
        this.m = board.length;
        this.n = board[0].length;

        // 从四条边上的 'O' 出发，标记所有与边界连通的 'O'
        for (int i = 0; i < m; i++) {
            dfs(i, 0);
            dfs(i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            dfs(0, j);
            dfs(m - 1, j);
        }

        // 遍历矩阵：'O' 翻转为 'X'，'#' 恢复为 'O'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    private void dfs(int i, int j) {
        // 越界或不是 'O' 则直接返回
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
            return;
        }
        // 标记为 '#'，表示与边界连通，不可翻转
        board[i][j] = '#';
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    }
}

func solve(board [][]byte) {
    m := len(board)
    if m == 0 {
        return
    }
    n := len(board[0])

    var dfs func(i, j int)
    dfs = func(i, j int) {
        // 越界或不是 'O' 则直接返回
        if i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O' {
            return
        }
        // 标记为 '#'，表示与边界连通，不可翻转
        board[i][j] = '#'
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    }

    // 从四条边上的 'O' 出发，标记所有与边界连通的 'O'
    for i := 0; i < m; i++ {
        dfs(i, 0)
        dfs(i, n-1)
    }
    for j := 0; j < n; j++ {
        dfs(0, j)
        dfs(m-1, j)
    }

    // 遍历矩阵：'O' 翻转为 'X'，'#' 恢复为 'O'
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == 'O' {
                board[i][j] = 'X'
            } else if board[i][j] == '#' {
                board[i][j] = 'O'
            }
        }
    }
}

解法二：BFS 反向标记

核心思路：

思路与解法一相同，区别在于使用 BFS（队列）替代 DFS（递归），避免矩阵较大时因递归深度过深导致栈溢出。

将四条边上的所有 ‘O’ 加入队列，逐层扩展，把所有连通的 ‘O’ 标记为 ‘#’。

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别为矩阵的行数和列数。

空间复杂度：O(m × n)，队列中最多存储所有格子。

{% raw %}

class Solution {

    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        Queue<int[]> queue = new LinkedList<>();

        // 将四条边上所有的 'O' 加入队列
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                queue.offer(new int[]{i, 0});
            }
            if (board[i][n - 1] == 'O') {
                queue.offer(new int[]{i, n - 1});
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                queue.offer(new int[]{0, j});
            }
            if (board[m - 1][j] == 'O') {
                queue.offer(new int[]{m - 1, j});
            }
        }

        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        // BFS 扩展，将所有与边界连通的 'O' 标记为 '#'
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int i = cell[0];
            int j = cell[1];
            if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
                continue;
            }
            board[i][j] = '#';
            for (int[] dir : dirs) {
                queue.offer(new int[]{i + dir[0], j + dir[1]});
            }
        }

        // 遍历矩阵：'O' 翻转为 'X'，'#' 恢复为 'O'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
}

{% endraw %}

{% raw %}

func solve(board [][]byte) {
    m := len(board)
    if m == 0 {
        return
    }
    n := len(board[0])

    type point struct{ i, j int }
    queue := []point{}

    // 将四条边上所有的 'O' 加入队列
    for i := 0; i < m; i++ {
        if board[i][0] == 'O' {
            queue = append(queue, point{i, 0})
        }
        if board[i][n-1] == 'O' {
            queue = append(queue, point{i, n - 1})
        }
    }
    for j := 0; j < n; j++ {
        if board[0][j] == 'O' {
            queue = append(queue, point{0, j})
        }
        if board[m-1][j] == 'O' {
            queue = append(queue, point{m - 1, j})
        }
    }

    dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

    // BFS 扩展，将所有与边界连通的 'O' 标记为 '#'
    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        i, j := cur.i, cur.j
        if i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O' {
            continue
        }
        board[i][j] = '#'
        for _, d := range dirs {
            queue = append(queue, point{i + d[0], j + d[1]})
        }
    }

    // 遍历矩阵：'O' 翻转为 'X'，'#' 恢复为 'O'
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == 'O' {
                board[i][j] = 'X'
            } else if board[i][j] == '#' {
                board[i][j] = 'O'
            }
        }
    }
}

{% endraw %}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	DFS/BFS、矩阵
417. 太平洋大西洋水流问题	中等	DFS/BFS、反向标记
695. 岛屿的最大面积	中等	DFS/BFS、矩阵
463. 岛屿的周长	简单	矩阵遍历
547. 省份数量	中等	DFS/BFS、并查集
733. 图像渲染	简单	DFS/BFS、矩阵
1020. 飞地的数量	中等	DFS/BFS、反向标记

本文作者: HGNULB

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