题解 | #迷宫问题#

每个位置进行前后左右试探前进，如果没超过临界值就入队列。因为队列的先进先出特性，所以会扩散着搜索 通过自定义Node类将到达终点的每个点串起来，顺序反转之后打印

//广度优先遍历
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Queue<Node> que = new LinkedList<>();
        Node head = new Node(0,0,null);
        int row = sc.nextInt();
        int col = sc.nextInt();
        int[][] nums = new int[row][col];
        for(int i = 0;i < row;i++){
            for(int j = 0;j < col;j++){
                nums[i][j] = sc.nextInt();
            }
        }
        que.add(head);
        while(!que.isEmpty()){
            //获取当前路径
            Node cur = que.poll();
            //记录当前路径坐标
            int i = cur.row;
            int j = cur.col;
            if(nums[i][j] == 1)
                continue;
            //标记当前路径
            nums[i][j] = 1;
            //判断是否走到终点
            if(i + 1 == row && j + 1 == col){
                reverseAndDisplay(cur);
                break;
            }
            //判断右边是否有路，有则入队列
            if(j < col - 1 && nums[i][j+1] != 1)
                //让当前路径与下一个路径相连接
                que.add(new Node(i,j+1,cur));
            //判断下边是否有路，有则入队列
            if(i < row - 1 && nums[i+1][j] != 1)
                que.add(new Node(i+1,j,cur));
            //判断左边
            if(j > 0 && nums[i][j-1] != 1)
                que.add(new Node(i,j-1,cur));
            //上
            if(i > 0 && nums[i-1][j] != 1)
                que.add(new Node(i-1,j,cur));
        }
    }
    private static void reverseAndDisplay(Node last){
        Node cur = last;
        while(cur.prev != null){
            cur.prev.next = cur;
            cur = cur.prev;
        }
        display(cur);
    }
    private static void display(Node head){
        Node cur = head;
        while(cur != null){
            cur.print();
            cur = cur.next;
        }
    }
    private static class Node{
        private final int row;
        private final int col;
        private Node next;
        private Node prev;
        public Node(int row,int col,Node prev){
            this.row = row;
            this.col = col;
            this.prev = prev;
        }
        private void print(){
            System.out.println("(" + row + "," + col + ")");
        }
    }
}