【Classic 150 刷题计划】 LeetCode 130. 被围绕的区域 | C++ 矩阵 DFS 与逆向边界保护法

LeetCode 130. 被围绕的区域

📌 题目描述

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

• 连接：一个单元格与水平或垂直方向上相邻的单元格连接。

• 区域：连接所有 'O' 的单元格来形成一个区域。

• 围绕：如果一个区域中的所有 'O' 单元格都不在棋盘的边缘，则该区域被包围。这样的区域完全被 'X' 单元格包围。
  通过 原地 将输入矩阵中的所有 '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"]]

💡 破题思路：逆向思维 (从边缘出发的 DFS 标记)

如果正向去检查每一个内部的 'O' 是不是被包围，需要处理大量的连通性边界，极其复杂。
大厂满分秘籍：逆向思维（保卫边区）
所有能够直接或间接和矩阵边缘的 'O' 连通的 'O'，都是绝对不可能被包围的“漏网之鱼”。

算法步骤：

💻 C++ 代码实现 (原汁原味作者版)

class Solution {
public:
// 方向向量：右、下、左、上
int dx[4] = {0, 1, 0, –1};
int dy[4] = {1, 0, –1, 0};

// ⚠️ 注意：固定大小的 st 数组在矩阵超过 210×210 时会越界
// 工业级建议直接在原地修改 board 字符（如改成 'A'）来省去 st 数组
int st[210][210];
int m, n;

void solve(vector<vector<char>>& board) {
m = board.size(), n = board[0].size();

// 1. 扫描四条边界，寻找所有与边缘相连的 'O'
for (int i = 0; i < m; i ++ )
for (int j = 0; j < n; j ++ )
{
if (board[i][j] == 'O')
{
// 如果当前点落在四条边界上，立刻触发 DFS 连通块标记
if (i == 0 || j == 0 || i == m – 1 || j == n – 1)
dfs(i, j, board);
}
}

// 2. 全局清剿：根据 st 状态重塑矩阵
for (int i = 0; i < m; i ++ )
for (int j = 0; j < n; j ++ )
{
if (st[i][j]) board[i][j] = 'O'; // 边缘连通的安全区，保留
else board[i][j] = 'X'; // 内部被包围的死区，全部杀死
}
}

void dfs(int x, int y, vector<vector<char>>& board)
{
st[x][y] = 1; // 标记为安全状态

for (int i = 0; i < 4; i ++ )
{
int xx = x + dx[i], yy = y + dy[i];
// 越界检查 + 必须是 'O' + 必须未被访问过
if (xx >= 0 && xx < m && yy >= 0 && yy < n && board[xx][yy] == 'O' && !st[xx][yy])
{
dfs(xx, yy, board);
}
}
}
};