130.被围绕的区域

题目:130.被围绕的区域

给你一个 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"]]

解释：
在上图中，底部的区域没有被捕获，因为它在 board 的边缘并且不能被围绕。

• 示例 2：

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

输出：[["X"]]

• 提示：

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

思路

1. 从边界开始标记：首先从矩阵的边缘开始，找到所有与边缘相连的 'O'，标记为 'Y'。因为这些 'O' 无法被围绕。
2. 遍历整个矩阵：在遍历矩阵时，将没有被标记的 'O' 变为 'X'（这些是被围绕的区域），将被标记为 'Y' 的字符复原为 'O'。
3. **深度优先搜索 (DFS)**：从边缘上的 'O' 开始，使用 DFS 标记所有与之相连的 'O'。

• 时间复杂度:O(mn)
• 空间复杂度:O(mn)

代码

public void solve(char[][] board) {
    int m = board.length;
    int n = board[0].length;
    // 从边界开始DFS，标记所有与边界相连的 'O'
    for (int i = 0; i < n; i++) {
        // 第一行
        dfs(0, i, board);
        // 最后一行
        dfs(m - 1, i, board);
    }
    for (int i = 0; i < m; i++) {
        // 第一列
        dfs(i, 0, board);
        // 最后一列
        dfs(i, n - 1, board);
    }
    // 遍历整个矩阵，将被标记的 'O' 恢复，将未被标记的 'O' 替换为 'X'
    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] == 'Y') {
                board[i][j] = 'O';
            }
        }
    }
}

private void dfs(int x, int y, char[][] board) {
    if (x < 0 || x > board.length - 1 || y < 0 || y > board[0].length - 1 || board[x][y] != 'O') {
        return;
    }
    // 标记当前 'O' 为 'Y'
    board[x][y] = 'Y';
    // 递归检查相邻的四个方向
    dfs(x - 1, y, board);
    dfs(x + 1, y, board);
    dfs(x, y - 1, board);
    dfs(x, y + 1, board);
}