题解 | #迷宫问题#

BFS求出最短距离，然后再逆序输出即可。

此题可以建模成一个无向无权网络，从起点开始最先搜索到的一定是到这个节点的最短距离。保存最短距离，此后再搜索到这个节点，必然不是最短距离，不用更新最短距离。

此题保证最短路径唯一，所以只需要从最后一个节点倒序搜索即可，只需要满足上一个节点的距离+1等于当前节点的距离，那么上一个节点必然是最短路径上的，保存到路径集合上，然后更新当前节点为上一个节点。

import java.util.*;

public class Main {
    
    static int n, m;
    static int[][] a;
    static Map<Node, Integer> dist = new HashMap<>();
    static int[] dx = new int[]{0,-1,0,1};
    static int[] dy = new int[]{1,0,-1,0};
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        a = new int[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        Node be = new Node(0,0);
        Node en = new Node(n-1,m-1);
        dist.put(be, 0);
        Queue<Node> q = new LinkedList<>();
        q.offer(be);
        while(q.size() > 0) {
            Node x = q.poll();
            if(x.equals(en)) {
                break;
            }
            for(int i = 0; i < 4; i++) {
                int aa = x.x + dx[i], bb = x.y + dy[i];
                if(aa >= 0 && aa < n && bb >= 0 && bb < m && a[aa][bb] == 0) {
                    Node ne = new Node(aa,bb);
                    if(dist.get(ne) == null) {
                        dist.put(ne, dist.get(x) + 1);
                        q.offer(ne);
                    }
                }
            }
        }
        List<Node> lst = new ArrayList<>();
        lst.add(en);
        Node now = en;
        while(!now.equals(be)) {
            for(int i = 0; i < 4; i++) {
                int aa = now.x + dx[i], bb = now.y + dy[i];
                if(aa >= 0 && aa < n && bb >= 0 && bb < m && a[aa][bb] == 0) {
                    Node ne = new Node(aa,bb);
                    if(dist.get(ne) != null && dist.get(ne) + 1 == dist.get(now)) {
                        lst.add(ne);
                        now = ne;
                        break;
                    }
                }
            }
        }
        for(int i = lst.size() - 1; i >= 0; i--) {
            System.out.println("(" + lst.get(i).x + "," + lst.get(i).y + ")");
        }
    }
}

class Node {
    int x, y;
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int hashCode() {
        return 1 << x + y;
    }
    public boolean equals(Object obj) {
        if(obj == null) {
            return false;
        }
        if(obj instanceof Node) {
            Node node = (Node)obj;
            return this.x == node.x && this.y == node.y;
        }
        return false;
    }
    
}