题目内容

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘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”]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：

输入：board = [[“X”]]
输出：[[“X”]]

提示

1、m == board.length
2、n == board[i].length
3、1 <= m, n <= 200
4、board[i][j] 为 ‘X’ 或 ‘O’

题解

本题可以采用深度优先遍历来做。具体的思想用到了逆向思维，即我们如果能找到不被围住的O，那么其他的O就一定是被围住的，可以改为X。具体做法如下：

1、使用二维布尔数组，记录哪些区域被遍历过。
2、枚举所有边界上的’O’，从该位置做Flood Fill，即做深度优先遍历，只遍历是’O’的位置，并将所有遍历到的位置都标记成true。
3、将所有未遍历到的位置变成’X’。

代码

class Solution {
public:
    vector<vector<char>> board;
    int n,m;
    int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};

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

        
        for(int i =0;i<n;i++){
            if(board[i][0] == 'O') dfs(i,0);
            if(board[i][m - 1] == 'O') dfs(i,m-1);
        }
        for(int i =0;i<m;i++){
            if(board[0][i] == 'O') dfs(0,i);
            if(board[n-1][i] == 'O') dfs(n-1,i);
        }
        for(int i = 0;i <n;i++){
            for(int j = 0;j<m;j++){
                if(board[i][j] == '#') board[i][j] = 'O';
                else board[i][j] = 'X';
            }
        }
        _board = board;
    }
    
    void dfs(int x,int y){
        board[x][y] = '#';
        for(int i = 0;i<4;i++){
            int a = x+dx[i],b=y+dy[i];
            if(a>=0 && a< n&&b>=0 &&b <m && board[a][b] == 'O')
                dfs(a,b);
        }
    }
};