leetcode 130. 被围绕的区域【BFS】【DFS】

1. 方法一：BFS
   本题可以逆向思考，若我把与边界的“O”相连的“O”全部找到，其他“O”全部替换为“X”即可。利用图的BFS算法找到所有与边界相连的“O”即可。

class Solution {
    private class Pos{
        public int x;
        public int y;
        public Pos(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}}; 
    public void solve(char[][] board) {
        int h = board.length;
        if(h<=0)return;
        int w = board[0].length;
        for(int i=0; i<h; i++){
            for(int j = 0; j<w; j++){
                if((i == 0 || i == h-1 || j==0 || j== w-1) && board[i][j] == 'O'){
                    bfs(board, i, j);
                }
            }
        }
        
        for(int i=0; i<h; i++){
            for(int j = 0; j<w; j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }else if(board[i][j] == '#'){
                    board[i][j] = 'O';
                }    
            }
        }
    }
    
    public void bfs(char[][] board, int i, int j){
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(i, j));
        board[i][j] = '#';
        while(!q.isEmpty()){
            Pos cur = q.poll();
            for(int k=0; k<4; k++){
                int newX = cur.x + dir[k][0];
                int newY = cur.y + dir[k][1];
                if(newX>=0 && newX <=board.length-1 && newY >=0 && newY <= board[0].length-1){
                    if(board[newX][newY] =='O'){
                        q.offer(new Pos(newX, newY));
                        board[newX][newY] = '#';
                    }
                }
            }
        }
    }
}

2. 方法二：DFS
   与方法1基本思想一致，搜索算法替换为DFS（深度优先搜索）

class Solution {
    private class Pos{
        public int x;
        public int y;
        public Pos(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}}; 
    public void solve(char[][] board) {
        int h = board.length;
        if(h<=0)return;
        int w = board[0].length;
        for(int i=0; i<h; i++){
            for(int j = 0; j<w; j++){
                if((i == 0 || i == h-1 || j==0 || j== w-1) && board[i][j] == 'O'){
                    dfs(board, i, j);
                }
            }
        }
        
        for(int i=0; i<h; i++){
            for(int j = 0; j<w; j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }else if(board[i][j] == '#'){
                    board[i][j] = 'O';
                }    
            }
        }
    }
    
    public void dfs(char[][] board, int i, int j){
        if(i<0 || j<0 ||  i>=board.length || j>=board[0].length  || board[i][j]!='O'){
            return;
        }
        if(board[i][j] == 'O'){
            board[i][j] = '#';
        }
        dfs(board, i-1, j);
        dfs(board, i+1, j);
        dfs(board, i, j-1);
        dfs(board, i, j+1);
    }
}