130. Surrounded Regions

class Solution {
    public void solve(char[][] board) {
        // one round dfs by search from the boundaries
        
        //search the '='
        for(int i=0; i<board.length;i++){
            dfs(board, i, 0);
            dfs(board, i, board[0].length-1);
        }
        //search the '||'
        for(int j=0; j<board[0].length; j++){
            dfs(board, 0, j);
            dfs(board, board.length-1, j);
        }
        
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                // change O before V
                if(board[i][j]=='O') board[i][j]='X';
                if(board[i][j]=='V') board[i][j]='O';
            }
        }
    }
    
    private void dfs(char[][] board, int i, int j){
        if(i<0 || j<0 || i>=board.length || j>=board[0].length){
            return;
        }
        if(board[i][j]=='X' || board[i][j]=='V') return;
        // mark 'O' to visited
        board[i][j]='V';
        dfs(board, i+1, j);
        dfs(board, i-1, j);
        dfs(board, i, j+1);
        dfs(board, i, j-1);
    }
}

class Solution {
    public void solve(char[][] board) {
        // two dfs:
        // first dfs to check if "O" is captured
        // second dfs to mark the not captured cell
        // finally revert the maked cell to O, and visited cell to X
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                if(!isCaptured(board, i, j)){
                    markNotCaptured(board, i, j);
                }
            }
        }
        
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                if(board[i][j]=='C') board[i][j]='O';
                if(board[i][j]=='V') board[i][j]='X';
            }
        }
    }
    
    private boolean isCaptured(char[][] board, int i, int j){
        if(i<0 || j<0|| i>=board.length || j>=board[0].length){
            return false;
        }
        // mark visited and connected cell as C
        if(board[i][j]=='C') return false;
        if(board[i][j]=='X' || board[i][j]=='V') return true;
        // mark as visited;
        board[i][j]='V';
        // return false if any of the recursions are false
        return isCaptured(board, i-1, j) && isCaptured(board, i+1, j) 
            && isCaptured(board, i, j-1) && isCaptured(board, i, j+1);
    }
    
    // recursively mark cell to 'C' is is not captured
    private void markNotCaptured(char[][] board, int i, int j){
        if(i<0 ||j<0 || i>=board.length || j>=board[0].length){
            return;
        }
        if(board[i][j]=='X' || board[i][j]=='C') return;
        
        board[i][j]='C';
        markNotCaptured(board, i-1, j);
        markNotCaptured(board, i+1, j);
        markNotCaptured(board, i, j-1);
        markNotCaptured(board, i, j+1);
    }
}