阴沟里翻船——学霸的迷宫

偏执的太偏执、 2022-08-21 04:27 85阅读 0赞

问题描述  
　　学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维  
的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计  
算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。  
输入格式  
　　第一行两个整数n， m，为迷宫的长宽。  
　　接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐  
标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据  
保证(1,1)，(n,m)可以通过。  
输出格式  
　　第一行一个数为需要的最少步数K。  
　　第二行K个字符，每个字符∈\{U,D,L,R\},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。  
样例输入  
Input Sample 1:  
3 3  
001  
100  
110

Input Sample 2:  
3 3  
000  
000  
000  
样例输出  
Output Sample 1:  
4  
RDRD

Output Sample 2:  
4  
DDRR  
数据规模和约定  
　　有20%的数据满足：1<=n,m<=10  
　　有50%的数据满足：1<=n,m<=50  
　　有100%的数据满足：1<=n,m<=500。

广搜常常用来求最短路径、最少操作之类的题目，迷宫最短路径更是广搜的经典题目。这道题虽说不仅要求最短步数，还要求字典序最小的路径，其实就是指定了搜索的顺序呗——D、L、R、U（分别对应下（1,0），左（0，-1），右（0,1），上（-1,0））。按这种顺序搜索，一旦到达终点，肯定就是所需的答案。我初次写还不放心，还特意加了一些if-else判断，可是后来考虑到广搜是一层一层搜的特点，就又注释了。  
然而，就是这样一道水题，我却阴沟里翻船了，因为一开始标记数组visited是置为false的，搜过后应该置为true的，可是我却不知道那根筋不对的又置为了false，结果当然是超时！！  
贴上代码，以供自戒、自律

import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    class Point{
        public int x,y,step;
        public String path=new String("");
        public Point(int x,int y,int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }
    
    public class Main {
    
        public static boolean DEBUG = true;
        public static int n,m;
        public static char[][] maze = new char[510][510];
        public static boolean[][] visited = new boolean[510][510];
        public final static int[] dirx = {
       1,0,0,-1} ;
        public final static int[] diry = {
       0,-1,1,0};
        public final static char[] dir = {
       'D','L','R','U'};
        //public static Queue<Point> que = new LinkedList<Point>();
        public static String ans ;
    
        public static void show(){
            System.out.println("Output maze:");
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++) System.out.print(maze[i][j]+" ");
                System.out.println();
            }
        }
        public static void test(){
            System.out.println("breakpoint!");
        }
        public static int BFS(){
            int ret = n*m+100;
            ans = new String("Z");
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++) visited[i][j] = false;
            }
            Point cur = new Point(0,0,0),next;
            Queue<Point> que = new LinkedList<Point>();
            que.clear();
            visited[0][0] = true;
            que.offer(cur);
            int nx,ny;
            while(!que.isEmpty()){
                cur = que.remove();
                //if(DEBUG) System.out.println(cur.x+","+cur.y+","+cur.step+","+cur.path);
                if(cur.x==n-1&&cur.y==m-1){
    // if(ret>cur.step){ 
    // ret = cur.step;
    // ans = cur.path;
    // }
    // else if(ret==cur.step&&ans.compareTo(cur.path)>0){ 
    // ans = cur.path;
    // }
    // else if(ret<cur.step) return ret;
                    ans = cur.path;
                    return cur.step;
                }
                else{
                    for(int i=0;i<4;i++){
       //
                        nx = cur.x + dirx[i];
                        ny = cur.y + diry[i];
                        if(nx>=0&&nx<n&&ny>=0&&ny<m&&!visited[nx][ny]&&maze[nx][ny]=='0'){
                            next = new Point(nx, ny, cur.step+1);
                            next.path = cur.path + dir[i];
                            visited[nx][ny] = true;
                            que.offer(next);
                        }
                    }
                }
            }
            return ret;
        }
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                n = in.nextInt();
                m = in.nextInt();
                String line = new String();
                for(int i=0;i<n;i++){
                    line = in.next();
                    maze[i] = line.toCharArray();
                }
                //show();
                long t1 = System.currentTimeMillis();
                int res = BFS();
                System.out.println(res);
                System.out.println(ans);
                long t2 = System.currentTimeMillis();
                //System.out.println("Time cost:"+(t2-t1));
            }
        }
    
    }