• Surrounded Regions

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.size()<=1 || board[0].size()<=1) return;

        int m=board.size(), n=board[0].size();
        deque<pair<int, int>> q;
        for(int i=0; i<n; i++){
            if(board[0][i]=='O')   q.push_back(make_pair(0, i));
            if(board[m-1][i]=='O') q.push_back(make_pair(m-1, i));
        }
        for(int i=1; i<m-1; i++){
            if(board[i][0]=='O')   q.push_back(make_pair(i, 0));
            if(board[i][n-1]=='O') q.push_back(make_pair(i, n-1));
        }

        while(!q.empty()){
            pair<int, int> temp=q.front();
            q.pop_front();
            board[temp.first][temp.second]='N';

            if(temp.first-1>=0 && board[temp.first-1][temp.second]=='O'){
                q.push_back(make_pair(temp.first-1, temp.second));
            }
            if(temp.first+1<m && board[temp.first+1][temp.second]=='O'){
                q.push_back(make_pair(temp.first+1, temp.second));
            }

            if(temp.second-1>=0 && board[temp.first][temp.second-1]=='O'){
                q.push_back(make_pair(temp.first, temp.second-1));
            }
            if(temp.second+1<n && board[temp.first][temp.second+1]=='O'){
                q.push_back(make_pair(temp.first, temp.second+1));
            }
        }

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(board[i][j]=='N')   board[i][j]='O';
                else if(board[i][j]=='O')   board[i][j]='X';
            }
        }

        return;
    }