leetcode130. 被围绕的区域

分析

从边界出发的O肯定不会被包围，所以只需要把边界点排除，剩下的都变成X即可。

class Solution {
public:
    int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
    void dfs(int i,int j,vector<vector<char>>& board){
        board[i][j]='A';
        int m=board.size(),n=board[0].size();
        for(int t=0;t<4;t++){
            int x=dx[t]+i,y=dy[t]+j;
            if(x>=0&&x<m&&y>=0&&y<n&&board[x][y]=='O'){
                board[x][y]='A';
                dfs(x,y,board);
            }
        }
    }
    void solve(vector<vector<char>>& board) {
        int m=board.size(),n=board[0].size();
        for(int i=0;i<n;i++){
              if(board[0][i]=='O')dfs(0,i,board);
              if(board[m-1][i]=='O')dfs(m-1,i,board);
        }
        for(int i=0;i<m;i++){
              if(board[i][0]=='O')dfs(i,0,board);
              if(board[i][n-1]=='O')dfs(i,n-1,board);
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]=='O')board[i][j]='X';
                else if(board[i][j]=='A')board[i][j]='O';
            }
        }
    }
};