130. Surrounded Regions

Solution

1. Change the 'O' on the edge of board into '#', since they are not going to be changed after all

2. Modify the remaining 'O' into 'X', they shall be changed after all

3. Recover the '#' into 'O'

Trying to DFS each edge element, in order to let all the 'O' connected with edge not been impacted.

T: O(MN)

 public void solve(char[][] board) {
        int row = board.length;
        if(row == 0) return;
        int col = board[0].length;
        
        for(int i = 0 ; i < row; i++){
            if(board[i][0] == 'O') helper(board, i, 0);
            if(board[i][col-1] == 'O') helper(board, i, col-1);
        }
        
        for(int j = 1; j < col; j++){
            if(board[0][j] == 'O') helper(board, 0, j);
            if(board[row-1][j] == 'O') helper(board, row-1, j);
        }
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
                else if(board[i][j] == '#'){
                    board[i][j] = 'O';
                }
            }
        }
        
    }
    public void helper(char[][] board, int i, int j){
        
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length
          || board[i][j] == '#' || board[i][j] == 'X')
            return;
        
        board[i][j] = '#';
        helper(board, i+1, j);
        helper(board, i-1, j);
        helper(board, i, j+1);
        helper(board, i, j-1);
    }