surrounded regions.

surrounded_regions.cpp

class Solution {
public:
/*

Surrounded Regions
Total Accepted: 12671 Total Submissions: 89715

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

*/
    void solve(vector<vector<char>> &board) {
        //search from a boundary O, mark its nabors as O, by BFS
        int m = board.size();
        if (m <= 0)
            return;
        int n = board[0].size();
        if (n <= 0)
            return;
        queue<pair<int, int> > Q_xy; 
        vector<vector<bool> > visited(m, vector<bool>(n, false));
        
        //first/last row
        for(int r=0; r<m; r+=max(1, m-1)) {
            for(int c=0; c<n; c+=1 ) {
                if (board[r][c] == 'O' && !visited[r][c])  {
                    visited[r][c] = true;
                    Q_xy.push(pair<int, int>(r, c));    
                }
            }
        }
        //first / last col
        for(int c=0; c<n; c+=max(1, n-1)) {
            for(int r=0; r<m; r+=1) {
                if (board[r][c] == 'O' && !visited[r][c])  {
                    visited[r][c] = true;
                    Q_xy.push(pair<int, int>(r, c));    
                }
            }
        }

        while (! Q_xy.empty() ) {
            pair<int, int> pIntInt = Q_xy.front();
            Q_xy.pop();
            int x = pIntInt.first;
            int y = pIntInt.second;
            //four nabors of x/y
            if (x-1>=0 && !visited[x-1][y] && board[x-1][y]=='O') { 
                visited[x-1][y] = true; Q_xy.push(pair<int,int>(x-1,y));
            }
            if (x+1< m && !visited[x+1][y] && board[x+1][y]=='O') { 
                visited[x+1][y] = true; Q_xy.push(pair<int,int>(x+1,y));
            }
            if (y-1>=0 && !visited[x][y-1] && board[x][y-1]=='O') { 
                visited[x][y-1] = true; Q_xy.push(pair<int,int>(x,y-1));
            }
            if (y+1< n && !visited[x][y+1] && board[x][y+1]=='O') { 
                visited[x][y+1] = true; Q_xy.push(pair<int,int>(x,y+1));
            }
        }
        
         for(int r=0; r<m; r+=1) {
            for(int c=0; c<n; c+=1) {
                if (board[r][c] =='O') {
                    if (!visited[r][c]) //not reachable from boundary
                        board[r][c]= 'X';
                }
            }
         }
         return;
    }
};