BFS

1.使用场景

BFS又称广度优先遍历，常用于寻找最短路径和迷宫最短路径的求解，也用于树的层次遍历等问题。

2.形象理解

我们可以把他想象成WIFI信号一样的存在（从一个小点不断向外一层一层的扩散）

我们也可以像理解走迷宫一样理解他

迷宫只能上下左右移动，青蓝色石砖不可走

例：从起点开始，走出的第一步只能是他的右边和下面的第一个格子的两种可能，这两个第一步又可以走自己四个不同方向的第二步

迷宫解题

1. 解题需要

1）一个整形二维数组搭建迷宫

2）一个判断二维数组判定是否遍历过了

3）一个队列来实现你在地图中的每一步走向情况

4）一个类或者一个结构体含有x，y的信息，若要求最短路径则加上最短路径信息

5）四个方向向量如dxy = [[1,0],[0,-1],[-1,0],[0,1]]分别表示右下左上

2. 解题步骤

1）将起始点添加进队列（头出）遍历状态变为true，当队列不为空时开启循环

2）取队列第一个元素，for循环四个方向向量（即上下左右移动）

3）当目的位置点为终点时，可结束

4）若不是终点，判断他有没有被遍历过并且不是障碍，则把这一点的

加入队列（尾进）

5）操作完队列第一个元素的上下左右信息后，把第一个元素弹出队列，再继续循环

注意:此链接视频一看就懂BFS步骤

实现代码

class Solution {
    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        int n = 1000;
        if(blocked.length<2){ return true;}
        //创建访问情况二维数组
        boolean[][] v = new boolean[n][n];
        //将地图初始化
        int[][] m = new int[n][n];
        for (int i = 0; i < blocked.length; i++) {
            for (int j = 0; j < blocked[i].length; j++) {
                if(blocked[i][j]!=0){m[i][j] = 1;}
            }
        }
        Point startPoint = new Point();
        startPoint.x = source[0];startPoint.y = source[1];

        //将头节点入队
        Queue<Point> queue = new LinkedList<>();
        queue.offer(startPoint);
        v[startPoint.x][startPoint.y] = true;
        //右下左上方向移动时分别的x的变动情况
        int[] dx ={0,1,0,-1};
        //右下左上方向移动时分别的y的变动情况
        int[] dy ={1,0,-1,0};
        while (!queue.isEmpty()){
            int x = queue.element().x,y = queue.element().y;
            //当节点为目标点时，返回true
            if(x == target[0]&& y == target[1]){
                return true;
            }
            for (int i = 0; i < 4; i++) {
                int tx,ty;
                tx = x + dx[i];
                ty = y + dy[i];
                //如果没被访问并不是障碍就入队列,并将访问状态更新为已经访问过了
                if(tx>=0&&ty>=0&&(!v[tx][ty]&&m[tx][ty]!=1)){
                    Point temp = new Point();
                    temp.x = tx;
                    temp.y = ty;
                    v[tx][ty] = true;
                    queue.add(temp);
                }
            }
            queue.remove();
        }
        return false;
    }
}

class Point{
    int x;
    int y;
}