$$\color{Red}{迷宫问题——BFS最短路}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

给定一个 n×n
的二维数组，如下所示：

int maze[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表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

数据保证至少存在一条从左上角走到右下角的路径。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含 n 个整数 0 或 1，表示迷宫。

输出格式

输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。

按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 (0,0)，右下角坐标为 (n−1,n−1)
。
数据范围

0 ≤ n ≤ 1000

输入样例：

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

输出样例：

0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4

思路

BFS为基础，而我们只需要把st数组，换成一个Pii数组，然后初始化的情况下，初始化坐标即可。

而为了防止开一个记录答案的数组，我们倒序搜答案，然后直接正序遍历，就不需要开额外的答案数组了。

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1010, n;
    static int[][] g = new int[N][N];
    static Pii[][] pre = new Pii[N][N];
    static Pii[] q = new Pii[N * N];

    static class Pii {
        int x, y;

        public Pii() {
        }

        public Pii(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void bfs(int x, int y) {
        int hh = 0, tt = 0;
        q[hh] = new Pii(x, y);
        pre[x][y] = new Pii(0, 0);
        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
        while (hh <= tt) {
            Pii t = q[hh++];
            for (int i = 0; i < 4; i++) {
                int a = t.x + dx[i], b = t.y + dy[i];
                if (a < 0 || a >= n || b < 0 || b >= n || g[a][b] == 1 || pre[a][b].x != -1) continue;
                q[++tt] = new Pii(a, b);
                pre[a][b] = t;
            }
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                g[i][j] = Integer.parseInt(s[j]);
                pre[i][j] = new Pii(-1, -1);
            }
        }
        bfs(n - 1, n - 1);
        Pii end = new Pii(0, 0);
        while (true) {
            System.out.println(end.x + " " + end.y);
            if (end.x == n - 1 && end.y == n - 1) break;
            end = pre[end.x][end.y];
        }
    }
}