2.走迷宫 - 蓝桥云课
bfs :我的理解就是按层数便利，便利完一层再遍历下一层
bfs:一般用来求解权相等的最短路径和最小操作数的问题
一般使用队列来实现
1.初始化队列 先将起始节点放入队列中
2.从队列中取出一个没有访问过的节点，将该节点的访问状态设置为已经访问，将这个节点的所有的邻居节点加入队列
3.确保每个节点都制备访问过一次，避免死循环
4.重复以上步骤，直到队列为空
假设所有 的边权都是1 （边权可以理解为相连 的两个点的距离 ，也就是一条边的长度）
1.首先先将1添加到队列中
然后访问1 的相邻节点
他们没有被 访问过，添加到队列中
1 现在已经被访问过了，就要把他移出队列
注意：队列中只存放没有访问过的元素
Queue [] 表示队列
dis表示起点到队中某一个元素的最短距离
1到1 本身的最短距离肯定是0 呀
1->2，3，4 的距离都是1
访问过的节点标成橙色
第一层便利完成了
然后开始便利第二层
注意：添加到队列中不代表这元素已经被访问过了
只有这个元素的相邻节点都添加到队列中了，才算这个元素被访问过了
我们每次只添加队头的相邻元素，然后添加完队头的相邻元素（注意：只添加没有访问过的元素，1虽然也是相邻元素，但是1已经被访问过了，所以添加1到队列），队头就算已经访问过了
现在队头是2 2 的相邻元素有1 ， 5 ，6 ，但是1已经被访问过了，所以把5和6两个没有访问过的元素添加到队尾，
距离数组dis 就是在2到1 的距离的基础上再加上5 到2 的距离和6 到2 的距离
此时2也已经被访问过了，取出队头元素2
现在队头元素是3，3 的相邻节点只有1 ，并且1 已经被访问过了，所以3没有可以添加的相邻节点，
现在3也访问过了，取出队头元素3
此时队头元素是4 ，同理将4 的没有被访问过的相邻节点添加到队列中
然后计算每一个添加的元素到起点的距离
该处理第三层元素了，5在队头，5没有未被访问过的节点，所以也不用添加，然后5也被访问过了，6同理
789也同理
队列为空结束访问，因为没有可以访问的节点了，就该结束了
总结：先将第一个元素放到队列中，然后进入循环，直到队列为空，结束循环
每次将队首的元素的取出，然后添加和队首元素相邻并且没有被访问过的元素到队尾，然后更新队列中的每一个元素到起点的最短距离
队首的元素不断变化，队尾的元素不断添加，最后直到每一个节点都被访问过，那么此队列中就无法添加元素了，队列中的元素就会不断的减少直到变成空队列。
迷宫问题的思路大概就是
回想一下我们刚才的思路
起点，终点
只要终点被访问过了是不是就是可以到达终点，
我们用两个数组来分别记录每个节点是否被访问过，以及每个节点到起点的最短路径
// 定义一个boolean数组来表示节点的访问状态boolean[][] v = new boolean[n+10][m+10];
// 定义一个二维的距离数组b来表示从起点到任意一个1个节点最短路径int[][] d = new int[n+10][m+10];一开始把所有节点到起点的都设置为不可达，也就是到起点的距离是无穷，直接设置成1e9 (1* 10 的9 次方)
//初始化所有最短路径为不可达状态 +无穷大的形式for (int i = 1; i <=n ; i++) {Arrays.fill(d[i], (int) 1e9);}然后再用一个队列来进行循环
然后用Queue（队列来存储）因为是二维的我们可以用Queue<Int[]>
// 队列用q表示
// 每个节点有两个坐标，队列中的节点开一个int数组类型
// 队列可以用LinkedList来表示Queue<int[]> q = new LinkedList<>();队列一般使用LinkedeList(处理首尾节点的时间复杂度都是O(1))
先把起点坐标x1y1 添加到队列中
// 先将起点放入队列中q.add(new int []{x1,y1});然后更新最短路径数组 中起点的值
// 从起点到起点的距离是0d[x1][y1] = 0;然后每一个位置是不是都可以上下左右移动
下面这个顺序是下上右左
//表示上下左右四个操作int dx[] = {0,0,1,-1};int dy[] = {1,-1,0,0};然后当队列非空的时候就进行循环判断
// 当队列非空的时候while (!q.isEmpty()){先取出队首元素分别获取横纵坐标
// 拿出队头元素int []o = q.poll();
// 当前节点的x和yint x = o[0],y =o[1];判断队首元素是否被访问过，如果被访问过，就判断队首元素的下一个元素
// 如果当前节点是已经访问状态,跳过这个节点访问下一个节点if(v[x][y]){continue;}如果没有被访问过的话，就把他标记成访问过
// 否则标记成已经访问的状态v[x][y] = true;记录这个队首元素的上下左右中的一种情况的相邻节点的坐标
int nx = dx[i] + x;int ny =dy[i] + y;判断坐标是否都满足这三个条件
有没有被访问过
v[nx][ny]是不是路障
g[nx][ny]==0有没有超出边界（起点按照1，1 终点按照n,m ）
nx>n || nx <1 || ny >m || ny < 1可达，也就是不满足以上条件
相邻节点的距离都是在队首元素到起点的最短距离的基础上加1 ，（某个点到旁边的点的距离）
在把这些节点添加到队列的末尾
else {d[nx][ny]= d[x][y] + 1;
// 在队列中添加新的相邻节点q.add(new int[]{nx,ny});}下面是循环判断的代码
// 当队列非空的时候while (!q.isEmpty()){
// 拿出队头元素int []o = q.poll();
// 当前节点的x和yint x = o[0],y =o[1];
// 如果当前节点是已经访问状态,跳过这个节点访问下一个节点if(v[x][y]){continue;}
// 否则标记成已经访问的状态v[x][y] = true;for (int i = 0; i <4 ; i++) {
// 表示相对于队首节点的坐标int nx = dx[i] + x;int ny =dy[i] + y;
// 超出了我们的边界
// 或者当前节点已经杯访问过了
// 或者当前节点是障碍物
// 不合法的if(nx>n || nx <1 || ny >m || ny < 1 || v[nx][ny] || g[nx][ny]==0){continue;}else {d[nx][ny]= d[x][y] + 1;
// 在队列中添加新的相邻节点q.add(new int[]{nx,ny});}}}最后循环结束判断终点x2,y2 是否被访问过，如果被访问过，就代表终点可达，就输出终点到起点的最短距离
如果没有被访问过就输出-1
// 判断重点是否可达if(!v[x2][y2]){System.out.println(-1);}else {System.out.println(d[x2][y2]);}最后下面是完整的代码，
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;/*** @author zb* date2025/3/25 18:22*/
public class Main{public static void main(String[] args) {Scanner in = new Scanner(System.in);
// 迷宫的大小int n = in.nextInt(),m =in.nextInt();int g[][] = new int[n+10][m+10];
// 表示是否为障碍物for (int i = 1; i <=n ; i++) {for (int j = 1; j <=m ; j++) {g[i][j] = in.nextInt();}}
// 入口和出口int x1 = in.nextInt(),y1 = in.nextInt();int x2 =in.nextInt(), y2 =in.nextInt();
// 定义一个boolean数组来表示节点的访问状态boolean[][] v = new boolean[n+10][m+10];
// 定义一个二维的距离数组b来表示从起点到任意一个1个节点最短路径int[][] d = new int[n+10][m+10];
//初始化所有最短路径为不可达状态 +无穷大的形式for (int i = 1; i <=n ; i++) {Arrays.fill(d[i], (int) 1e9);}
// 从起点到起点的距离是0d[x1][y1] = 0;
// 队列用q表示
// 每个节点有两个坐标，队列中的节点开一个int数组类型
// 队列可以用LinkedList来表示Queue<int[]> q = new LinkedList<>();
// 先将起点放入队列中q.add(new int []{x1,y1});
//表示上下左右四个操作int dx[] = {0,0,1,-1};int dy[] = {1,-1,0,0};// 当队列非空的时候while (!q.isEmpty()){
// 拿出队头元素int []o = q.poll();
// 当前节点的x和yint x = o[0],y =o[1];
// 如果当前节点是已经访问状态,跳过这个节点访问下一个节点if(v[x][y]){continue;}
// 否则标记成已经访问的状态v[x][y] = true;for (int i = 0; i <4 ; i++) {
// 表示相对于队首节点的坐标int nx = dx[i] + x;int ny =dy[i] + y;
// 超出了我们的边界
// 或者当前节点已经杯访问过了
// 或者当前节点是障碍物
// 不合法的if(nx>n || nx <1 || ny >m || ny < 1 || v[nx][ny] || g[nx][ny]==0){continue;}else {d[nx][ny]= d[x][y] + 1;
// 在队列中添加新的相邻节点q.add(new int[]{nx,ny});}}}// 判断重点是否可达if(!v[x2][y2]){System.out.println(-1);}else {System.out.println(d[x2][y2]);}in.close();}
}
