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

unlocked question, 所以不貼截圖了

這道題的意思是 當(dāng)一坨(可以是一個(gè) 也可以是好幾個(gè)連在一起的) ‘O’ 四周都被‘X'包圍時(shí)若治，把這些‘O’改成X改衩；而當(dāng)這一坨不是四周都有‘X’時(shí)，讓它還是‘O'鹅士。注意 只有這一坨‘O’在board的邊緣的時(shí)候，他才可以不被四周環(huán)繞泛烙。既然如此锨推，思路就出來(lái)了座韵，我們從board的四個(gè)邊緣開始便利，當(dāng)出現(xiàn)‘O'的時(shí)候堤舒，我們做BFS色建，搜索出跟這個(gè)’O‘挨在一起的同伙們，并且標(biāo)記這些為‘B’舌缤。在我們從board的四周遍歷完所有的元素之后箕戳，滿足條件的‘O’就都被標(biāo)記為‘B'了；而未遍歷到的’O‘ 也就是四周被’X'包圍起來(lái)的‘O’仍然是‘O'友驮。 所以最后漂羊，遍歷整個(gè)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';
            }
        }
    }
};