dfs 求最短路并将路径打印出来

思想：从终点到起点dfs, 另开一个数组记录当前点是从哪个点转移而来

import java.io.*;
import java.util.*;
class Main {
    static int N = 1010;
    static int n;
    static int[][] g = new int[N][N];
    static Place[][] d = new Place[N][N];
    static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    static class Place {
        int x, y;
        Place (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static void bfs(int x, int y) {
        Queue<Place> q = new LinkedList<>();
        q.offer(new Place(x, y));
        while (!q.isEmpty()) {
            Place p = q.poll();
            if (p.x == 0 && p.y == 0) break;
            for(int i = 0; i < 4; i++) {
                int a = p.x + dx[i], b = p.y + dy[i];
                if (a >= 0 && a < n && b >= 0 && b < n && g[a][b] == 0 && d[a][b] == null) {
                    q.offer(new Place(a, b));
                    d[a][b] = p;
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        for (int i = 0; i < n; i++) {
            s = cin.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                g[i][j] = Integer.parseInt(s[j]);
            }
        }

        bfs(n - 1, n - 1);

        Place end = new Place(0, 0);
        while (true) {
            System.out.println(end.x + " " + end.y);
            if (end.x == n - 1 && end.y == n - 1) break;
            end = d[end.x][end.y];
        }

    }
}