130. 被圍繞的區(qū)域
難度：中
題目概述：找到所有被包圍的區(qū)域，并更改其坐標(biāo)值。
thicky：題目解釋中說，邊界的0不會(huì)被填充。所以這道題并不是找被包圍的區(qū)域，而是找的不能被包圍的區(qū)域。
不能被包圍的區(qū)域則必然是從矩形的邊界為起點(diǎn)。
題解1：DFS
1）將邊界的O為起點(diǎn)，搜索與其相連的O，統(tǒng)一記錄為F，代表false，即不被包圍。
2）全圖中，除了F以外，其余的O均被包圍，需要改為。
3）DFS流程和標(biāo)準(zhǔn)模板一致。

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return;
        int row = board.size(), col = board[0].size();
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (i == 0 || i == row - 1 || j == 0 || j == col - 1) {
                    if (board[i][j] == 'O') dfs(board, i , j);
                }
            }   
        }
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == 'F') board[i][j] = 'O';
            }
        }
    }
    void dfs(vector<vector<char>> &board, int x, int y) {
        int row = board.size(), col = board[0].size();
        vector<vector<int>> dir{{0,-1},{-1,0},{0,1},{1,0}};
        board[x][y] = 'F';
        for (int i = 0; i < dir.size(); ++i) {
            int dx = x + dir[i][0], dy = y + dir[i][1];
            if (dx >= 0 && dx < row && dy >= 0 && dy < col && board[dx][dy] == 'O') {
                dfs(board, dx, dy);
            }
        }
    }
};

題解2：BFS
1）將邊界的O為起點(diǎn)，搜索與其相連的O，統(tǒng)一記錄為F，代表false，即不被包圍。
2）思路和DFS的一樣，只不過操作手法采用了BFS。

class Solution {
public:

    void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return;
        vector<vector<int>> dir = {{1,0},{0,-1},{-1,0},{0,1}};
        int row = board.size(), col = board[0].size();
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (i != 0 && i != row - 1 && j != 0 && j != col - 1) continue;
                if (board[i][j] != 'O') continue;
                board[i][j] = 'F';
                queue<pair<int,int>> q; 
                q.push({i, j});
                while (!q.empty()) {
                    pair<int,int> cur = q.front(); q.pop();
                    int x = cur.first, y = cur.second; 
                    for (int i = 0; i < dir.size(); i++) {
                        int x = cur.first + dir[i][0];
                        int y = cur.second + dir[i][1];
                        if (x > 0 && x < row - 1 && y > 0 && y < col - 1 && board[x][y] == 'O') {
                            board[x][y] = 'F';
                            q.push({x, y});
                        }
                    }
                }
            }
        }
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == 'F') board[i][j] = 'O';
            }
        }
    }
};