java---BFS算法---走迷宫（每日一道算法2022.8.22）

题目
给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁

最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置
请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次
数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路

输入：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
1
2
3
4
5
6
7

输出：
8
1
2

public class BFS_走迷宫 {
    //初始化, g是存的地图，d存的是每个点到起点的距离,切记n和m是在外面先定义，要不然bfs调不到
    //q是在模拟队列，n代表x轴值，m代表y轴值
    public static int N = 110, n, m;
    public static int[][] g = new int[N][N], d = new int[N][N];
    public static Pair[] q = new Pair[N*N];

    public static void main(String[] args) {
        //初始化，将地图存入g数组
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); m = in.nextInt();
        for (int i = 0; i<n; i++){
            for (int j = 0; j<m; j++){
                g[i][j] = in.nextInt();
            }
        }

        System.out.println(bfs());
    }
    public static int bfs(){
        //在q中添加第一步，也就是00位置，hh和tt是模拟队列的队头和队尾
        //将d中所有元素替换为-1代表都没走过，00位设为0代表走过了
        //dx和dy代表上下左右四个方向，枚举一遍, 向下是0，-1，向上是0，1，向左是-1，0，向右是1，0
        int hh = 0, tt = 0;
        q[0] = new Pair(0, 0);
        for (int[] i : d) {Arrays.fill(i, -1);}
        d[0][0] = 0;
        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};

        //队列不为空时，取出队头元素
        while (hh<=tt) {
            Pair head = q[hh++];
            for (int i = 0; i<4; i++){
                int x = head.x + dx[i], y = head.y + dy[i];
                //这里判断x和y首先要在边界内，并且在g数组为0说明可以走，再就是这个点在d数组为-1也就是之前没走过
                if (x>=0 && x<n && y>=0 && y<m && g[x][y] == 0 && d[x][y] == -1) {
                    //从起始点到这个点的步数
                    d[x][y] = d[head.x][head.y] + 1;
                    q[++tt] = new Pair(x, y);
                }
            }
        }
        //最后输出右下角的这个点就可以了
        return d[n-1][m-1];
    }
}

class Pair{
    int x;
    int y;
    public Pair(int x, int y) {
        this.x = x; this.y = y;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

图例：

今天鼠标坏了，触控有问题，没有备用鼠标凑合着，血压飙升，各种误触，脑壳痛

声明：算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流