LeetCode 面试经典150题 [81/150 被围绕的区域]

题目描述

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

个人C++解答

class Solution {
public:
void dfs(vector<vector<char>>& board, int i, int j) {
        int i_num = board.size();
        int j_num = board[0].size();
 
        board[i][j] = '-';
 
        if (i - 1 >= 0 && board[i - 1][j] == 'O')
            dfs(board, i - 1, j);
        if (i + 1 < i_num && board[i + 1][j] == 'O')
            dfs(board, i + 1, j);
        if (j - 1 >= 0 && board[i][j - 1] == 'O')
            dfs(board, i, j - 1);
        if (j + 1 < j_num && board[i][j + 1] == 'O')
            dfs(board, i, j + 1);
    }
    void solve(vector<vector<char>>& board) {
        int i_num = board.size();
        int j_num = board[0].size();
        for(int j=0;j<j_num;j++){
            if(board[0][j]=='O'){
                dfs(board,0,j);
            }
        }
        for(int j=0;j<j_num;j++){
            if(board[i_num-1][j]=='O'){
                dfs(board,i_num-1,j);
            }
        }
        for(int i=0;i<i_num;i++){
            if(board[i][0]=='O'){
                dfs(board,i,0);
            }
        }
        for(int i=0;i<i_num;i++){
            if(board[i][j_num-1]=='O'){
                dfs(board,i,j_num-1);
            }
        }
        for(int i=0;i<i_num;i++){
            for(int j=0;j<j_num;j++){
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == '-') board[i][j] = 'O';
            }
        }

    }
};