被围绕的区域

七崽爱吃小饼干2026/01/11阅读 0专栏算法合集

被围绕的区域

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

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

通过原地将输入矩阵中的所有 'O' 替换为 'X' 来捕获被围绕的区域。你不需要返回任何值。

示例 1：

codeType

输入：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：

codeType

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

输出：[['X']]

提示：

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

解法

/**
 Do not return anything, modify board in-place instead.
 */

const dfs = (board: string[][], y: number, x: number) => {
    board[y][x] = 'I'
    const h = board.length
    const w = board[0].length
    if(x - 1 >= 0 && board[y][x - 1] === 'O') dfs(board, y, x - 1) // 左
    if(x + 1 < w && board[y][x + 1] === 'O') dfs(board, y, x + 1) // 右
    if(y - 1 >= 0 && board[y - 1][x] === 'O') dfs(board, y - 1, x) // 下
    if(y + 1 < h && board[y + 1][x] === 'O') dfs(board, y + 1, x) // 上
}

function solve(board: string[][]): void {
    // 只有边缘的'O'才不会被捕获
    // 可以额外定义一个状态I，表示属于未被捕获的区域
    // 只针对边缘的"O"进行深搜，然后标记为I
    // 最后再遍历整个矩阵，将'O'变成'X' ,'I'变成'O'
    const h = board.length
    if(h <= 2) return // 两行以下都不会被捕获
    const w = board[0].length

    for(let i = 0; i < h; i++){
        for(let j = 0; j < w; j++){
            if(i === 0 || i === h - 1 || j === 0 || j === w - 1){
                // 第一行或最后一行或第一列或最后一列
                if(board[i][j] === 'O') dfs(board, i, j)
            }
        }
    }
    for(let i = 0; i < h; i++){
        for(let j = 0; j < w; j++){
            board[i][j] = board[i][j] === 'I' ? 'O' : 'X'
        }
    }
};