题解 | 迷宫问题

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int h=sc.nextInt();
        int w=sc.nextInt();
        int[][]grid=new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                grid[i][j]=sc.nextInt();
                // if(grid[i][j]==1){
                //     grid[i][j]=Integer.MAX_VALUE;
                // }
            }
        }   
        int[][]dis=new int[h][w];
        for (int i = 0; i < dis.length; i++) {
            Arrays.fill(dis[i], Integer.MAX_VALUE/2);
        }
        dis[0][0]=0;
        Queue<int[]>que=new ArrayDeque<>();
        boolean[][]vis=new boolean[h][w];
        que.add(new int[]{0,0,0});
        vis[0][0]=true;
        int[][]parent=new int[h][w];
        parent[0][0]=-1;
        int[][]dirs={{-1,0},{1,0},{0,-1},{0,1}};
        while (!que.isEmpty()) {
            int[]cur=que.poll();
            for (int[] d : dirs) {
                int nx=cur[0]+d[0];
                int ny=cur[1]+d[1];
                int val=cur[2];
                if(nx>=0&&ny>=0&&nx<h&&ny<w&&grid[nx][ny]!=1&&!vis[nx][ny]){
                    vis[nx][ny]=true;
                    parent[nx][ny]=cur[0]*100+cur[1];
                    dis[nx][ny]=val+1;
                    que.add(new int[]{nx,ny,val+1});
                }
            }
        }
        int x=h-1,y=w-1;
        List<int[]>list=new ArrayList<>();
        list.add(new int[]{x,y});
        while (parent[x][y]!=-1) {
            int val=parent[x][y];
            int nx=val/100;
            int ny=val%100;
            x=nx;
            y=ny;
            list.add(new int[]{x,y});
        }
        for (int i = list.size()-1; i >=0; i--) {
            int[]cur=list.get(i);
           System.out.println("("+cur[0]+","+cur[1]+")");
        }
        sc.close();
    }
}