康瑞部落

Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

解题思路：

这道题的含义是将所有被X包围的O置为X（向围棋那样的包围）。注意到要想某个“O”被包住，那么至少要三行三列。

我们从四个边入手，将所有与边中某个O联通的O标记为“#”，然后将非标记的“O”置为X，最后将“#”恢复成“O”。递归算法（DFS）算法的代码如下：

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if(m<3){
            return;
        }
        int n = board[0].size();
        if(n<3){
            return;
        }
        for(int i=0; i<m; i++){
            if(board[i][0] == 'O'){
                setFlag(board, m, n, i, 0);
            }
            if(board[i][n-1] == 'O'){
                setFlag(board, m, n, i, n-1);
            }
        }
        for(int i=0; i<n; i++){
            if(board[0][i] == 'O'){
                setFlag(board, m, n, 0, i);
            }
            if(board[m-1][i] == 'O'){
                setFlag(board, m, n, m-1, i);
            }
        }
        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]=='#'){
                    board[i][j]='O';
                }
            }
        }
    }
    
    void setFlag(vector<vector<char>>& board, int& m, int& n, int i, int j){
        if(i<0||i>=m || j<0 || j>=n){
            return;
        }
        if(board[i][j]=='O'){
            board[i][j] = '#';
            setFlag(board, m, n, i+1, j);
            setFlag(board, m, n, i-1, j);
            setFlag(board, m, n, i, j+1);
            setFlag(board, m, n, i, j-1);
        }
    }
};

但是倘若矩阵很大，就会产生错误，原因可能是递归过深会产生错误。

那么我们应该采用迭代的方法BFS

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        //只有行列数均大于等于3才能形成包围圈
        int m = board.size();
        if(m<3){
            return;
        }
        int n = board[0].size();
        if(n<3){
            return;
        }
        queue<int> qx;
        queue<int> qy;
        for(int i=0; i<m; i++){
            if(board[i][0] == 'O'){
                qx.push(i);
                qy.push(0);
            }
            if(board[i][n-1] == 'O'){
                qx.push(i);
                qy.push(n-1);
            }
        }
        for(int i=0; i<n; i++){
            if(board[0][i] == 'O'){
                qx.push(0);
                qy.push(i);
            }
            if(board[m-1][i] == 'O'){
                qx.push(m-1);
                qy.push(i);
            }
        }
        while(!qx.empty()){
            int x = qx.front();
            int y = qy.front();
            qx.pop();
            qy.pop();
            if(board[x][y]!='O'){
                continue;
            }
            board[x][y]='#';
            if(x>0 && board[x-1][y]=='O'){
                qx.push(x-1);
                qy.push(y);
            }
            if(x<m-1 && board[x+1][y]=='O'){
                qx.push(x+1);
                qy.push(y);
            }
            if(y>0 && board[x][y-1]=='O'){
                qx.push(x);
                qy.push(y-1);
            }
            if(y<n-1 && board[x][y+1]=='O'){
                qx.push(x);
                qy.push(y+1);
            }
        }
        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]=='#'){
                    board[i][j]='O';
                }
            }
        }
    }
};