LeetCode 八月打卡day11 130. 被围绕的区域（DFS）

思路：

我们可以先对边界上的’O’进行DFS，将所有’O’先修改为其他字符，这里取了’Y’字符。 对四条边搜索完后剩下的’O修改为’X’字符后，我们再将’Y’字符修改为’O’字符，就能得到正确答案。

代码：

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