/*
    思路：
        两遍bfs，第一遍查看是否被包围;
        如若被包围开始第二遍bfs，将改个连通块全部设置为'X'
*/
class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int n = board.size();
        //  特判，一般leetcode的数据很多都有[]
        if(n == 0)  return ;
        int m = board[0].size();
        bool vis[n][m];
        memset(vis, false, sizeof vis);
        typedef pair<int, int> pii;
        int dic[4][2] = {
            {-1, 0}, {1, 0}, {0, -1}, {0, 1}
        };
        for(int i = 0; i < n; i ++ ){
            for(int j = 0; j < m; j ++ ){
                int flag = false;
                if(!vis[i][j] && board[i][j] == 'O'){
                    queue<pii> qu;
                    qu.push({i, j});
                    vis[i][j] = true;
                    while(!qu.empty()){
                        pii now = qu.front();
                        qu.pop();
                        for(int i = 0; i < 4; i ++ ){
                            int xx = now.first + dic[i][0];
                            int yy = now.second + dic[i][1];
                            if(xx < 0 || xx >= n || yy < 0 || yy >= m){
                                // cout << xx << yy << endl;
                                flag = true;
                                continue;
                            }
                            if(board[xx][yy] == 'O' && !vis[xx][yy]){
                                vis[xx][yy] = true;
                                qu.push({xx, yy});
                            }
                        }
                    }
                    //  被包围(重置)
                    if(!flag){
                        queue<pii> qu;
                        qu.push({i, j});
                        board[i][j] = 'X';
                        while(!qu.empty()){
                            pii now = qu.front();
                            qu.pop();
                            for(int i = 0; i < 4; i ++ ){
                                int xx = now.first + dic[i][0];
                                int yy = now.second + dic[i][1];
                                if(xx < 0 || xx >= n || yy < 0 || yy >= m)  continue;
                                if(board[xx][yy] == 'X')    continue;
                                board[xx][yy] = 'X';
                                qu.push({xx, yy});
                            }
                        }
                    }
                }else   continue;
            }
        }
    }
};