LeetCode 130. Surrounded Regions

[Surrounded Regions](https://leetcode.com/submissions/detail/66979297/)

unlocked question, 所以不贴截图了

这道题的意思是 当一坨(可以是一个 也可以是好几个连在一起的) ‘O’ 四周都被‘X'包围时，把这些‘O’改成X；而当这一坨不是四周都有‘X’时，让它还是‘O'。注意 只有这一坨‘O’在board的边缘的时候，他才可以不被四周环绕。既然如此，思路就出来了，我们从board的四个边缘开始便利，当出现‘O'的时候，我们做BFS，搜索出跟这个’O‘挨在一起的同伙们，并且标记这些为‘B’。在我们从board的四周遍历完所有的元素之后，满足条件的‘O’就都被标记为‘B'了；而未遍历到的’O‘ 也就是四周被’X'包围起来的‘O’仍然是‘O'。 所以最后，遍历整个board，把’B‘改成’O'，‘O改成’X‘。 That's it!. OMG This is long code. I dont even realize it until I pasted it. You could also use a vector to store left/right/up/down element of current element and then iterate these four element if you think it would be better :)

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty())
            return;
        auto row(board.size()), column(board[0].size());
        // iterate up margin and down margin
        for (auto i = 0; i < column; i++) {
            if (board[0][i] == 'O')             bfs(board, 0, i);
            if (board[row - 1][i] == 'O')       bfs(board, row - 1, i);
        }
        // iterate left margin and right margin
        for (auto i = 0; i < row; i++) {
            if (board[i][0] == 'O')             bfs(board, i, 0);
            if (board[i][column - 1] == 'O')    bfs(board, i, column - 1);
        }
        for (auto i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (board[i][j] == 'B')         board[i][j] = 'O';
                else if (board[i][j] == 'O')    board[i][j] = 'X';
            }
        }
    }
private:
    void bfs(vector<vector<char>>& board, unsigned long r, unsigned long c) {
        auto row(board.size()), column(board[0].size());
        queue<pair<int, int>> que;
        que.push(make_pair(r, c));
        board[r][c] = 'B';
        while(!que.empty()) {
            auto cur = que.front();
            que.pop();
            // current row and current column
            int curr(cur.first), curc(cur.second);
            // up element
            if (curr > 0 && board[curr - 1][curc] == 'O') {
                que.push(make_pair(curr - 1, curc));
                board[curr - 1][curc] = 'B';
            }
            // down element
            if (curr < row - 1 && board[curr + 1][curc] == 'O') {
                que.push(make_pair(curr + 1, curc));
                board[curr + 1][curc] = 'B';
            }
            // left element
            if (curc > 0 && board[curr][curc - 1] == 'O') {
                que.push(make_pair(curr, curc - 1));
                board[curr][curc - 1] = 'B';
            }
            // right element
            if (curc < column - 1 && board[curr][curc + 1] == 'O') {
                que.push(make_pair(curr, curc + 1));
                board[curr][curc + 1] = 'B';
            }
        }
    }
};