题解 | 迷宫问题

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    static class Point{

        private int x,y,z;
        public Point(int x,int y,int z)
        {
            this.x=x;
            this.y=y;
            this.z=z;
        }

    }
    private  static int h,w;
    private static int [][] direction={{0,1},{1,0},{0,-1},{-1,0}};
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别

        h= in.nextInt();
        w = in.nextInt();



        // 构造迷宫
        int[][] map = new int[h][w];
        int[][] map1 = new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                map1[i][j]=map[i][j] = in.nextInt();
            }
        }
        List<Point> fromPath =new ArrayList<>();
        List<Point> toPath =new ArrayList<>();
        bfs(map,0,0,1,fromPath);
//        System.out.println();

        bfs(map1,h-1,w-1,-1,toPath);

        List<Point> path =new ArrayList<>();

        Set<Point> set =new HashSet<>();

        while (toPath.size()>0 && fromPath.size()>0)
        {
            Point toP =toPath.get(0);
            Point  fromP = fromPath.get(fromPath.size() - 1);
            Point remove;
            if(fromP.x==toP.x && fromP.y==toP.y)
            {

                path.add(toP);
                toPath.remove(0);
                fromPath.remove(fromPath.size() - 1);

            }
            else {
                boolean find =false;

                for (Point point : fromPath) {
                    if(point.x==toP.x && point.y==toP.y)
                    {
                        find=true;
                        break;

                    }
                }
                if (!find)
                {
                    toPath.remove(0);
                    continue;

                }
                remove= fromPath.remove(fromPath.size() - 1);
                set.add(remove);

                for (Point point : set) {
                    if(point.x==toP.x && point.y==toP.y)
                    {
                        toPath.remove(0);
                        break;
                    }
                }
//                if(!find)
//                {
//                    toPath.remove(0);
//                }




            }

//            remove = fromPath.remove(fromPath.size() - 1);
//            set.add(remove);
        }
        // System.out.println();

        for (int i = path.size()-1; i >=0 ; i--) {
            System.out.println("("+path.get(i).x+","+path.get(i).y+")");

        }




    }


    public static void bfs(int[][] map,int x,int y,int order,List<Point> path)
    {
        int count=0;
        Queue<Point> que =new ArrayDeque<>();
        Point p =new Point(x,y,count++);

        map[x][y]=2;
        que.offer(p);
        while(!que.isEmpty())
        {

            Point cur =que.peek();
            path.add(cur);
//            System.out.println("(" + cur.x + "," + cur.y +","+cur.z+ ") ");
            que.poll();
            if (cur.x==h-1 && cur.y==w-1 && order==1)
            {
                return;
            }
            if (cur.x==0 && cur.y==0 && order==-1)
            {
                return;
            }


            for(int i=0;i<4;i++)
            {
                int nextX =cur.x+direction[i][0];
                int nextY =cur.y+direction[i][1];
                if(nextX<0||nextX>h-1||nextY<0||nextY>w-1)
                {
                    continue;
                }
                if(map[nextX][nextY]==0)
                {
                    que.offer(new Point(nextX,nextY,count++));
                    map[nextX][nextY]=2;

                }


            }

        }


    }


}

正走再倒走，找到合理的路径上的点