130 Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter 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

Solution

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if ( m == 0 ) return;
        int n = board[0].size();
        if (n == 0 ) return;
        stack<pair<int, int>> s;
        for ( int i = 0; i <= m-1; i++ ) {
            if (board[i][0] == 'O' ) s.push(pair<int, int>(i, 0));
            if (board[i][n-1] == 'O' ) s.push(pair<int, int>(i, n-1));
        }
        for ( int j = 0; j <= n-1; j++ ) {
            if (board[0][j] == 'O' ) s.push(pair<int, int>(0, j));
            if (board[m-1][j] == 'O' ) s.push(pair<int, int>(m-1, j));
        }
        while( ! s.empty() ) {
            int n1 = s.top().first, n2 = s.top().second;
            s.pop();
            board[n1][n2] = '-';
            if ( n1-1 >= 0 and board[n1-1][n2] == 'O' ) s.push(pair<int, int>(n1-1, n2));
            if ( n1+1 <= m-1 and board[n1+1][n2] == 'O' ) s.push(pair<int, int>(n1+1, n2));
            if ( n2-1 >= 0 and board[n1][n2-1] == 'O' ) s.push(pair<int, int>(n1, n2-1));
            if ( n2+1 <= n-1 and board[n1][n2+1] == 'O' ) s.push(pair<int, int>(n1, n2+1));
        }
        for (int i = 0; i <= m-1; i++ ) {
            for ( int j = 0; j <= n-1; j++ ) {
                if ( board[i][j] == 'O' ) board[i][j] = 'X';
                if ( board[i][j] == '-' ) board[i][j] = 'O';
            }
        }
        return;
    }
};

Notes

• BFS do not need to recover the path. (Not going back!)
• Mark all the "on-edge" O by -. Do another scan to convert non-marked O to X; and convert - back to O.