130. Surrounded Regions (Graph; DFS)

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

思路：从四条边上的'0'入手，与其邻接的'O'都不被改，记为'D'。逆向思维！从不被改的'O'入手，而非寻找被改得'O'

class Solution {
public:   
    void dfs(int x, int y){
        if(x<0 || x>=m || y<0 || y>=n || board[x][y]!='O') return;
        board[x][y]='D';

        //图的四个方向遍历
        dfs(x-1,y);
        dfs(x+1,y);
        dfs(x,y-1);
        dfs(x,y+1);
    }
    
    void solve(vector<vector<char>> &board){
        if (board.empty()) return;
        this->board = board;
        m=board.size();
        n=board[0].size();
        if(n<=2 || m<=2) return;
        
        for(int j=0;j<n;j++){
            dfs(0,j);
            dfs(m-1,j);
        }
        
        for(int i=1;i<m;i++){
            dfs(i,0);
            dfs(i,n-1);
        }
        
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(this->board[i][j]=='O') this->board[i][j]='X';
                else if(this->board[i][j]=='D') this->board[i][j]='O';
            }  
      board = this->board;
    }
private: 
    int m,n;
    vector<vector<char>> board;
};