题解 | #被围绕的区域#

由于不想用dfs写，就想了个别的。

这里使用类似于并查集的思想，首先将原本O的位置置位X，并且对于所有O的位置进行记录。记录完毕后对board周围的元素先进行复原，然后从先从左上角开始根据O的记录表参考逐一复原O，然后在从右下角开始往左上角开始逐一复原（矩形对称性）。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @return char字符型vector<vector<>>
     */
    
        vector<vector<char> > surroundedArea(vector<vector<char> >& board) {
        // write code here
        int n = board[0].size();
        vector<int> bc(board.size()*board[0].size(),-1);
        for(int i = 0; i<board.size(); ++i){
            for(int j =0; j<board[0].size();++j){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                    bc[i*n+j] = 1;
                }
            }
        }
        
        for(int i = 0; i<n;++i){
            if(bc[i] != -1)
                board[0][i] = 'O';
            if(bc[i*n] != -1)
                board[i][0] = 'O';
            if(bc[(n-1)*n+i] != -1)
                 board[n-1][i] = 'O';
            if(bc[n*i+n-1] != -1)
                 board[i][n-1] = 'O';
        }
       for(int i = 0; i<board.size(); ++i){
            for(int j = 0; j<board[0].size();++j){
                    if(i>0 && board[i-1][j]=='O' && bc[i*n+j]!=-1)
                        board[i][j] = 'O';
                    if(j>0 && board[i][j-1]=='O' && bc[i*n+j]!=-1)
                        board[i][j] = 'O';
                }
            }
        for(int i = n-1; i>=0; --i){
            for(int j = n-1; j>=0;--j){
                    if(i<n-1 && board[i+1][j]=='O' && bc[i*n+j]!=-1)
                        board[i][j] = 'O';
                    if(j<n-1 && board[i][j+1]=='O' && bc[i*n+j]!=-1)
                        board[i][j] = 'O';
                }
            }
        return board;
    }
};