题目：https://leetcode-cn.com/problems/surrounded-regions/
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

我的方法一，广度优先搜索

步骤

思路是先找到边上的O，然后深度所有和这个O相连的所有的O；等遍历完了所有边上的O后，剩余没有遍历的O就是被围绕的区域。

1. 先将所有的边上的O的坐标存到一个队列里
2. 从队列获取一个O，然后对这个O进行深度优先搜索相连的O，搜索到的O也存到这个队列里
3. 在这个过程中，有可能一个O可能会被遍历多次，所以为了只遍历一次，所以遍历后，先暂时改为一个特殊的字符，如A
4. 当队列里没有O时，即所有的和边相连的O都没有的时候，剩余的O就是被围绕的
5. 将所有被围绕的O改为X；将所有的A再改为O

边界条件

1. 注意矩阵的长或者宽为0
2. 遍历时需要考虑坐标越界
3. 当队列为空时，说明所有的和边相连的O遍历完，即停止遍历即可

复杂度

时间复杂度：O(n)，如下代码注释，需要注意深度搜索时，由于使用A对遍历过的O进行特殊标记，所以一个O只会被遍历一次，所以深度搜索也是O(n)。
空间复杂度：队列最多放入n个点，所以也是O(n)。

代码

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};

        int row = board.size();
        if(row==0){
            return;
        }
        int col = board[0].size();
        if(col==0){
            return;
        }
        
        //O(n)
        queue<pair<int, int>> edge_q;//y, x
        for(int x = 0; x<col; x++){
            if(board[0][x] == 'O'){
                edge_q.emplace(0, x);
            }
            if(board[row-1][x] == 'O'){
                edge_q.emplace(row-1, x);
            }
        }

        for(int y = 0; y<row; y++){
            if(board[y][0] == 'O'){
                edge_q.emplace(y, 0);
            }
            if(board[y][col-1] == 'O'){
                edge_q.emplace(y, col-1);
            }
        }

        int tmp_y;
        int tmp_x;
        //dfs, O(n)
        while(!edge_q.empty()){
            pair<int, int> top = edge_q.front();
            edge_q.pop();

            board[top.first][top.second] = 'A';

            for(int i=0; i<4; i++){
                tmp_y = top.first+dy[i];
                tmp_x = top.second+dx[i];
                if(tmp_y>=0 && tmp_y<row && tmp_x>=0&& tmp_x<col && board[tmp_y][tmp_x] == 'O'){
                    edge_q.emplace(tmp_y, tmp_x);
                }
            }
        }

        //O(n)
        for(int x = 0; x<col; x++){
            for(int y = 0; y<row; y++){
                if(board[y][x] == 'O'){
                    board[y][x] = 'X';
                }
            }
        }

        //O(n)
        for(int x = 0; x<col; x++){
            for(int y = 0; y<row; y++){
                if(board[y][x] == 'A'){
                    board[y][x] = 'O';
                }
            }
        }
    }
};

我的方法二，深度优先搜索

在BFS基础上，稍微改下就是，代码如下

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};

        int row = board.size();
        if(row==0){
            return;
        }
        int col = board[0].size();
        if(col==0){
            return;
        }
        
        //O(n)
        queue<pair<int, int>> edge_q;//y, x
        for(int x = 0; x<col; x++){
            if(board[0][x] == 'O'){
                edge_q.emplace(0, x);
            }
            if(board[row-1][x] == 'O'){
                edge_q.emplace(row-1, x);
            }
        }

        for(int y = 0; y<row; y++){
            if(board[y][0] == 'O'){
                edge_q.emplace(y, 0);
            }
            if(board[y][col-1] == 'O'){
                edge_q.emplace(y, col-1);
            }
        }

        while(!edge_q.empty()){
            pair<int, int> o = edge_q.front();
            edge_q.pop();
            dfs(board, row, col, o.first, o.second);
        }

        //O(n)
        for(int x = 0; x<col; x++){
            for(int y = 0; y<row; y++){
                if(board[y][x] == 'O'){
                    board[y][x] = 'X';
                }
            }
        }

        //O(n)
        for(int x = 0; x<col; x++){
            for(int y = 0; y<row; y++){
                if(board[y][x] == 'A'){
                    board[y][x] = 'O';
                }
            }
        }
    }

private:
    void dfs(vector<vector<char>>& board, int row, int col, int y, int x) {
        if(y<0 || y>= row || x<0 || x>= col || board[y][x] != 'O'){
            return;
        }

        board[y][x] = 'A';
        dfs(board, row, col, y - 1, x);
        dfs(board, row, col, y + 1, x);
        dfs(board, row, col, y, x - 1);
        dfs(board, row, col, y, x + 1);
    }
};

我的方法三，迭代版DFS

方法二是一个尾递归，所以很容易改成迭代，代码如下

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int row = board.size();
        if(row==0){
            return;
        }
        int col = board[0].size();
        if(col==0){
            return;
        }
        
        //O(n)
        queue<pair<int, int>> edge_q;//y, x
        for(int x = 0; x<col; x++){
            if(board[0][x] == 'O'){
                edge_q.emplace(0, x);
            }
            if(board[row-1][x] == 'O'){
                edge_q.emplace(row-1, x);
            }
        }

        for(int y = 0; y<row; y++){
            if(board[y][0] == 'O'){
                edge_q.emplace(y, 0);
            }
            if(board[y][col-1] == 'O'){
                edge_q.emplace(y, col-1);
            }
        }

        while(!edge_q.empty()){
            pair<int, int> o = edge_q.front();
            edge_q.pop();

            stack<pair<int, int>> s;//参数栈
            s.push(o);//模拟首次调用dfs设置的参数

            pair<int, int> param;
            while(!s.empty()){//参数栈为空时，说明递归完成了
                param = s.top();
                s.pop();

                //模拟dfs函数里的判断
                if(param.first<0 || param.first>= row || param.second<0 || param.second>= col || board[param.first][param.second] != 'O'){
                    continue;
                }

                board[param.first][param.second] = 'A';

                //模拟4次调用dfs
                s.emplace(param.first - 1, param.second);
                s.emplace(param.first + 1, param.second);
                s.emplace(param.first, param.second + 1);
                s.emplace(param.first, param.second - 1);
            }
        }

        //O(n)
        for(int x = 0; x<col; x++){
            for(int y = 0; y<row; y++){
                if(board[y][x] == 'O'){
                    board[y][x] = 'X';
                }
            }
        }

        //O(n)
        for(int x = 0; x<col; x++){
            for(int y = 0; y<row; y++){
                if(board[y][x] == 'A'){
                    board[y][x] = 'O';
                }
            }
        }
    }
};