【leetcode】BFS&DFS系列

 

目录

一、Leetcode130. Surrounded Regions

---

 

一、Leetcode130. Surrounded Regions

思路：

1.判断边界是否为0，是的话BFS判断前后左右邻居是否为0，是的话说明是连通的，都设置为#(方便整体遍历时替换为0)

2.遍历整个二维数组，把剩余的没联通的0都变为X，最后把#都设置为0，完事~

/**
 * @name: L130.class
 * @Author :
 * @create :   2020-06-21
 * @Desc: 1.先判断是否边界为o，是的话，就bfs判断前后左右，是o就可连通，设为#，不是就不变
 * 2.之后把#换位o，o的换为x，即可
 */
public class L130 {

        public void solve(char[][] board){
            if(board.length ==0 || board == null) return;
            int nr = board.length, nc = board[0].length; //行数，列数
            boolean isEdge;

            for (int i=0; i<nr;i++){
                for (int j=0;j<nc;j++){
                    isEdge = (i == 0 || i== nr-1 || j==0 ||j==nc-1); //边界
                    if(isEdge && board[i][j] == 'O')
                        bfs(board, i ,j); //每次遇到o就向前后左右搜索
                }
            }

            for (int i=0; i<nr;i++){
                for (int j=0;j<nc;j++){
                    if(board[i][j] == 'O') board[i][j] = 'X';
                    if(board[i][j] == '#') board[i][j] = 'O';
                }
            }
        }


        public void bfs(char[][] board, int x ,int y){
            Queue<Pos> posQueue = new LinkedList<>();
            posQueue.add(new Pos(x,y));
            board[x][y] = '#';
            Pos pos = null;
            while (!posQueue.isEmpty()){
                pos = posQueue.poll(); //获取并删除第一个

               // pos的上方是o的话，加入队列，并且数组变为#
                if (pos.row-1>=0 && board[pos.row-1][pos.col] == 'O'){
                    posQueue.add(new Pos(pos.row-1, pos.col));
                    board[pos.row-1][pos.col] = '#';
                }

               // 下方是o，
                if (pos.row+1 <= board.length-1 && board[pos.row+1][pos.col] == 'O'){
                    posQueue.add(new Pos(pos.row+1, pos.col));
                    board[pos.row+1][pos.col] = '#';
                }

                //右方
                if (pos.col+1 <= board[0].length-1 && board[pos.row][pos.col+1] == 'O'){
                    posQueue.add(new Pos(pos.row, pos.col+1));
                    board[pos.row][pos.col+1] = '#';
                }

               //左方
                if (pos.col-1 >=0 && board[pos.row][pos.col-1] == 'O'){
                    posQueue.add(new Pos(pos.row, pos.col-1));
                    board[pos.row][pos.col-1] = '#';
                }
            }

        }



        class Pos{
            int row;
            int col;

            public Pos(int row, int col) {
                this.row = row;
                this.col = col;
            }
        }  
}