题解 | #迷宫问题#

import java.util.*;

public class Main {

      public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int hang = in.nextInt();
        int lie = in.nextInt();
        int[][] db = new int[hang][lie];
        for (int i = 0; i < hang; i++) {
            for (int j = 0; j < lie; j++) {
                db[i][j] =in.nextInt();
            }
        }

        HashMap<String, String> father = new HashMap<>();  // 用map来存储  可以不用链表  记录当前节点和父节点

        int[][] visited = new int[hang][lie];
        //
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{0, 0});

        while (!queue.isEmpty()){
            int[] peek = queue.poll();
            bfs(peek,db,queue,visited,father);
        }

        Stack  result= new Stack();
        String lastNode="(" + (hang-1) + "," + (lie-1) + ")";
        result.push(lastNode);


        while (true){
            String temp = father.get(lastNode);
            if (temp!=null){
                lastNode=temp;
                result.push(temp);
            }
            if (lastNode.equals("(0,0)") ) {
                break;
            }
        }

        while (!result.isEmpty()){
            System.out.println(result.pop());
        }

    }

    public static void  bfs(int[] start,int[][] db, Queue<int[]> queue,int[][] visited,HashMap<String, String> father){
        // 他这个其实是有一个定位了方向 我这么写也是可以的  可以不用方向来进行实现    算距离的时候  我可以定义一个类point 来做最后的相加   但是如果不用类  用最原始的c的做法呢
        Integer x =start[0];
        Integer y =start[1];

        if (x==db.length-1 && y==db[0].length-1){
            // 走到了边界
            return ;
        }

        // 否则向右走
        if (y+1< db[0].length &&  db[x][y+1]==0 && visited[x][y+1]==0 ){
            queue.add(new int[]{x,y+1});
            visited[x][y+1]=1;
            int temp=y+1;
            father.put("(" + x + "," + temp + ")", "(" + x + "," + y + ")");
        }
        // 向下走
        if (x+1< db.length && db[x+1][y]==0   && visited[x+1][y]==0  ){
            queue.add(new int[]{x+1,y});
            visited[x+1][y]=1;

            int temp=x+1;
            father.put("(" + temp+ "," + y + ")", "(" + x + "," + y + ")");
        }
        // 向左
        if (y<=0){
            return;
        }

        if ( y-1>=0  &&  db[x][y-1]==0 && visited[x][y-1]==0 ){
            queue.add(new int[]{x,y-1});
            visited[x][y-1]=1;
            int temp=y-1;
            father.put("(" + x + "," + temp + ")", "(" + x + "," + y + ")");
        }

        // 向上
        if (x<=0){
            return ;
        }
        if (x-1>=0 && db[x-1][y]==0 && visited[x-1][y]==0){
            queue.add(new int[]{x-1,y});
            visited[x-1][y]=1;
            int temp=x-1;
            father.put("(" + temp + "," + y + ")", "(" + x + "," + y + ")");
        }
        return;
    }

}