题解 | #被围绕的区域#

解决思路很妙：对边界进行dfs，以边界为起点，搜索到的O都不应该被替换成X，其他的O都可以被替换成X

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @return char字符型vector<vector<>>
     */
    vector<vector<char> > surroundedArea(vector<vector<char> >& board) {
        // write code here
        int m = board.size();
        int n = board[0].size();
        
        for(int i=0; i<m; i++){
            dfs(board, m, n, i, 0);
            dfs(board, m, n, i, n-1);
        }
        for(int i=0; i<n; i++){
            dfs(board, m, n, 0, i);
            dfs(board, m, n, m-1, i);
        }
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(board[i][j] == 'A'){
                    board[i][j] = 'O';
                }
                else if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
        return board;
    }
    
    void dfs(vector<vector<char> >& board, int m, int n, int cur_i, int cur_j){
        if(cur_i<0 || cur_i>=m || cur_j<0 || cur_j>=n){
            return;
        }
        if(board[cur_i][cur_j] == 'X' || board[cur_i][cur_j] == 'A'){
            return;
        }
        
        if(board[cur_i][cur_j] == 'O'){
            board[cur_i][cur_j] = 'A';
        }
        dfs(board, m, n, cur_i-1, cur_j);
        dfs(board, m, n, cur_i+1, cur_j);
        dfs(board, m, n, cur_i, cur_j-1);
        dfs(board, m, n, cur_i, cur_j+1);
    }
    
};