Surrounded Regions

Surrounded Regions

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

---------------------------------- thinking ----------------------------------------------------------

If you are using a queue, make sure not to enqueue the already marked element's neighbors in your bfs:

if board[p[0]][p[1]] == 'S':
    continue

Below shows why queue brings duplication without the lines above:

Suppose a, b, c, d, e, f all marked with 'O' and line up as:

 a   b   c
 d   e   f

Now if current queue has ab in it, then the queue goes as follow:

ab --> bbd --> bdce --> dcece --> cecee --> eceff --> cefff --> effff --> fffff --> ... --> STOP

What happens when it is stack?

ab --> ace --> acdf --> acdc --> acd --> ac --> a --> STOP

As you can see, stack also brings in duplicates, but because dfs goes as deep as possible, the duplicates are much fewer than those in queue.

----------------------------------- codes --------------------------------------------------------------
class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if (board.size() <= 2 || board[0].size() <= 2) {
            return;
        }
        int width = board[0].size();
        int height = board.size();
        int visits[2] = {0, height - 1};
        for (int j = 0; j < 2; j++) {
            for (int i = 0; i < width; i++) {
                if (board[visits[j]][i] == 'O') {
                    travNode(visits[j], i, board);
                }
            }
        }
        visits[1] = width - 1;
        for (int i = 0; i < 2; i++) {
            for (int j = 1; j < height - 1; j++) {
                if (board[j][visits[i]] == 'O') {
                    travNode(j, visits[i], board);
                }
            }
        }
        for (int j = 0; j < height; j++) {
            for (int i = 0; i < width; i++) {
                if (board[j][i] == 'O') {
                    board[j][i] = 'X';
                }
                if (board[j][i] == ' ') {
                    board[j][i] = 'O';
                }
            }
        }
        return;
    }
    void travNode(int j, int i, vector<vector<char>> &board) {
        stack<pair<int, int>> stack;
        stack.push(make_pair(j, i));
        while (stack.size()) {
            pair<int, int> cur = stack.top();
            stack.pop();
            board[cur.first][cur.second] = ' ';
            if (cur.first-1 >= 0 && board[cur.first-1][cur.second] == 'O') {
                stack.push(make_pair(cur.first-1, cur.second));
            }
            if (cur.first+1 < board.size() && board[cur.first+1][cur.second] == 'O') {
                stack.push(make_pair(cur.first+1, cur.second));
            }
            if (cur.second-1 >= 0 && board[cur.first][cur.second-1] == 'O') {
                stack.push(make_pair(cur.first, cur.second-1));
            }
            if (cur.second+1 < board[0].size() && board[cur.first][cur.second+1] == 'O') {
                stack.push(make_pair(cur.first, cur.second+1));
            }
        }
    }
};