130. Surrounded Regions

//从edge往中间搜O的位置 mark成E 是所有不可改成X的pos
// second pass change all Es to O and Os to X
//DFS
class Solution {
    private int[][] dir ={{1,0},{0,1},{-1,0},{0,-1}};
    public void solve(char[][] board) {
        if(board.length < 2 || board[0].length < 2) return;
        for(int row = 0; row < board.length ; ++row) {
            for(int col = 0; col < board[0].length; ++col){
                if((row == 0 || row == board.length -1 || col==0  || col == board[0].length-1) && board[row][col] == 'O'){
                    dfsFromEdge(row,col,board);
                }
            }
        }
        for(int row = 0; row < board.length ; ++row) {
            for(int col = 0; col < board[0].length; ++col){
                if(board[row][col] == 'O'){
                    board[row][col] = 'X';
                }else if(board[row][col] == 'E'){
                    board[row][col] = 'O';
                }
            }
        }



    }
    void dfsFromEdge(int x, int y, char[][] board){
        board[x][y] = 'E';
        for(int i = 0 ;i < 4;++i){
            int newX = x+dir[i][0];
            int newY = y+dir[i][1];
             if(newX<0 || newY<0 || newX>=board.length || newY>= board[0].length) continue;
             if(board[newX][newY] == 'O'){
                dfsFromEdge(newX,newY,board);
            }
        }
    }
}