04、被围绕的区域

厨子大约 4 分钟数据结构算法算法基地面试深搜广搜刷题

哈喽，大家好，我是厨子，今天给大家说一个经典题目，被围绕的区域

https://leetcode.cn/problems/surrounded-regions/open in new window

题目描述

给你一个 m x n 的矩阵 board，由若干字符 'X' 和 'O' 组成，捕获所有被围绕的区域：

连接：一个单元格与水平或竖直方向上相邻的单元格连接。
区域：连接所有 'O' 的单元格形成一个区域。
围绕：如果您可以用 'X' 单元格连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 'X' 单元格围绕。

通过将输入矩阵 board 中的所有 'O' 替换为 'X' 来捕获被围绕的区域。

示例 1:

输入：board = [
  ["X","X","X","X"],
  ["X","O","O","X"],
  ["X","X","O","X"],
  ["X","O","X","X"]
]

输出：[
  ["X","X","X","X"],
  ["X","X","X","X"],
  ["X","X","X","X"],
  ["X","O","X","X"]
]

解释：
被围绕的区域不应该在边界上。
在示例中，只有位于中心的 "O" 被 "X" 围绕，
因此它们被替换为 "X"。
底部的 "O" 没有被围绕（它在边界上），所以保留。

示例 2:

输入：board = [["X"]]
输出：[["X"]]

约束条件:

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 'X' 或 'O'

题目很容易理解，就是将位于中心位置被 X 包围的 O 修改为 X，也就是这块全为 O 的区域，四周全为 X 才符合咱们的要求，下面看详细讲解

什么是被围绕的区域？

被围绕区域的定义：
1. 由 'O' 组成的连通区域
2. 不与边界相连
3. 四周被 'X' 包围

示例分析：
X X X X
X O O X
X X O X
X O X X

区域1: 中间的三个 'O'
  O O
    O
→ 被 X 完全围绕 ✓
→ 不接触边界 ✓
→ 应该被替换为 X

区域2: 底部的 'O'
    O
→ 接触边界 ✗
→ 不应该被替换

反向思维 ⭐

正向思维（困难）：
找出所有被围绕的 'O' → 复杂

反向思维（简单）：
找出所有不被围绕的 'O' → 简单
→ 不被围绕 = 与边界相连

算法步骤：
1. 从边界的 'O' 开始搜索
2. 标记所有与边界相连的 'O'
3. 剩余的 'O' 就是被围绕的
4. 替换为 'X'

问题分析

核心难点

难点1: 如何判断 'O' 是否被围绕？
解决: 反向思考，找不被围绕的

难点2: 如何标记与边界相连的 'O'？
解决: 从边界开始 DFS/BFS

难点3: 如何避免误判？(我们后面还需要将其改回 O，所以需要使用临时标记)
解决: 使用临时标记（如 '#'）

DFS（深度优先搜索）⭐⭐⭐

算法步骤

步骤1: 标记阶段
从四条边界出发，DFS 标记所有与边界相连的 'O'
标记为特殊字符（如 '#'）

步骤2: 替换阶段
遍历整个矩阵：
- 遇到 'O' → 替换为 'X'（被围绕的）
- 遇到 '#' → 还原为 'O'（不被围绕的）

图解分析

原始矩阵：
X X X X
X O O X
X X O X
X O X X

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

步骤1: 从边界开始 DFS 标记

检查上边界（第 0 行）：
X X X X  → 没有 'O'

检查下边界（第 3 行）：
X O X X
  ↑
  找到 'O'，开始 DFS(与这个 O 相连的 O，都是不被包围的)

DFS(3,1):
X X X X
X O O X
X X O X
X # X X
  ↑
标记为 '#'，向上递归

DFS(2,1): grid[2][1] = 'X'，停止

检查左边界（第 0 列）：
X
X
X
X
→ 没有 'O'

检查右边界（第 3 列）：
X
X
X
X
→ 没有 'O'

标记后的矩阵：
X X X X
X O O X
X X O X
X # X X

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

步骤2: 替换阶段

遍历矩阵：
- 'O' → 'X'（被围绕的）
- '#' → 'O'（边界连通的）

最终矩阵：
X X X X
X X X X
X X X X
X O X X

解释：
- 中间的三个 'O' 被替换为 'X'（被围绕）
- 底部的 'O' 保留（与边界相连）

代码实现

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) {
            return;
        }

        m = board.size();
        n = board[0].size();

        // 从边界开始 DFS 标记
        // 上边界和下边界
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                dfs(board, 0, j);       // 上
            }
            if (board[m-1][j] == 'O') {
                dfs(board, m-1, j);   // 下
            }
        }

        // 左边界和右边界
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);       // 左
            }
            if (board[i][n-1] == 'O') {
                dfs(board, i, n-1);   // 右
            }
        }

        // 替换
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';  // 被围绕的 O
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O';  // 边界连通的 O
                }
            }
        }
    }

private:
    int m, n;

    void dfs(vector<vector<char>>& board, int i, int j) {
        // 边界检查
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
            return;
        }

        // 标记为 '#'
        board[i][j] = '#';

        // 四个方向递归
        dfs(board, i - 1, j);  // 上
        dfs(board, i + 1, j);  // 下
        dfs(board, i, j - 1);  // 左
        dfs(board, i, j + 1);  // 右
    }
};