题解 57| 城里的人想逃，外面的人想进#被围绕的区域#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @return char字符型vector<vector<>>
     */
    void dfs(vector<vector<char>> &board,int x,int y){
        if (x < 0 || x >= board.size() ||
            y < 0 || y >= board[0].size()) 
        {
            return;//出界了
        }

        if (board[x][y] == 'O') {
            board[x][y] = 'B';

            dfs(board, x-1, y);
            dfs(board, x+1, y);
            dfs(board, x, y+1);
            dfs(board, x, y-1);
        }
    }
    vector<vector<char> > surroundedArea(vector<vector<char> >& board) {
        // write code here
        if(board.empty()) return board;
        int b = board.size();

        //上下y深度扫描
        for (int i = 0; i < b; ++i) {
            dfs(board, 0, i);
            dfs(board, board.size()-1, i);
        }

        //左右x深度扫描
        for (int i = 0; i < b; ++i) {
            dfs(board, i, 0);
            dfs(board, i, board.size()-1);
        }
        
        for (int i = 0; i < b; ++i) {
            for (int j = 0; j < b; ++j) {
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
                if(board[i][j] == 'B'){
                    board[i][j] = 'O';//还原
                }

            }
        }

        return board;
    }
};

基本算法思想

使用深度优先搜索（DFS）来遍历与边界上的 'O' 相连的所有 'O'，将其标记为 'B'。然后再遍历整个矩阵，将 'O' 替换为 'X'，将 'B' 替换为 'O'。

时间复杂度：

假设矩阵的大小为 m x n，遍历矩阵的时间复杂度为 O(mn)，DFS的时间复杂度为 O(mn)。所以总的时间复杂度为 O(mn)。

空间复杂度：

使用了递归调用的DFS算法，所以空间复杂度为递归调用栈的深度，最坏情况下为 O(mn)。