题解 | #迷宫问题#

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int[][] grd = new int[a + 2][b + 2];//在地图外包围一圈1，便于判断
        //地图初始化
        for (int i = 1; i <= a; i++) {
            for (int j = 1; j <= b; j++) {
                int t = in.nextInt();
                grd[i][j] = t;
            }
        }
        
        for (int i = 0; i < a + 2; i++) {
            grd[i][0] = 1;
            grd[i][b + 1] = 1;
        }
        for (int j = 0; j < b + 2; j++) {
            grd[0][j] = 1;
            grd[a + 1][j] = 1;
        }
        //初始化队列 链表表头 节点指针
        Queue<Node> que  = new LinkedList<Node>();
        Node head = new Node(1, 1, null);
        que.offer(head);
        Node temp;
        //广度优先搜索
        do {
            
            temp = que.poll();
            grd[temp.a][temp.b] = 1;//走过的坐标换成1

            if (grd[temp.a + 1][temp.b] == 0) {//下
                Node node = new Node(temp.a + 1, temp.b, temp);
                que.offer(node);
            }
            if (grd[temp.a - 1][temp.b] == 0) {//上
                Node node = new Node(temp.a - 1, temp.b, temp);
                que.offer(node);
            }
            if (grd[temp.a][temp.b + 1] == 0) {//右
                Node node = new Node(temp.a, temp.b + 1, temp);
                que.offer(node);
            }
            if (grd[temp.a][temp.b - 1] == 0) {//左
                Node node = new Node(temp.a, temp.b - 1, temp);
                que.offer(node);
            }

        } while (!(temp.a == a && temp.b == b));
        //用栈来存储以及将反向查找的路径归正
        Stack<Node> res = new Stack<Node>();
        do{
            res.push(temp);
            temp = temp.pre;
        }while(temp.pre != null);
        System.out.println("(0,0)");//起点
        do{
            Node out = res.pop();
            int ao = out.a -1;
            int bo = out.b -1;
            System.out.println("("+ao+","+bo+")");
        }while(!res.isEmpty());
    }
}

class Node {//用pre代替next，节点指向上一个节点，便于反推最短路径
    int a;
    int b;
    Node pre;
    public Node(int a, int b, Node pre) {
        this.a = a;
        this.b = b;
        this.pre = pre;
    }
}