BFS-学霸的迷宫

旧城等待， 2023-07-14 08:27 2阅读 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。

import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class 学霸的迷宫 {
        
        static int n,m;
        static char[][]a;
        static class node{
        
            int x,y;
            String s="";
        }
        static boolean [][]flag;
        static int[][]vis={
        {
        0,0,1,-1},{
        1,-1,0,0}};//右左上下RLUD
        static void bfs(int x,int y){
        
            Queue<node> queue=new LinkedList<>();
            node p=new node();
            flag[x][y]=true;
            p.x=x;
            p.y=y;
            queue.offer(p);
            while (!queue.isEmpty()){
        
                node now=queue.element();
                queue.poll();
                for (int i = 0; i <4 ; i++) {
        
                    int x1=now.x+vis[0][i];
                    int y1=now.y+vis[1][i];
                    if (x>=1&&y>=1&&x<=n&&y<=m&&!flag[x1][y1]&&a[x1][y1]=='0'){
        
                        node pp=new node();
                        pp.x=x1;
                        pp.y=y1;
                        if (i==0) pp.s=now.s+'R';
                        else if (i==1) pp.s=now.s+'L';
                        else if (i==2) pp.s=now.s+'D';
                        else pp.s=now.s+'U';
                        queue.offer(pp);
                        if (x1==n&&y1==m){
        
                            System.out.println(pp.s.length());
                            System.out.println(pp.s);
                            System.exit(0);
                        }
                    }
                }
            }
        }
        public static void main(String[] args) {
        
            Scanner scanner=new Scanner(System.in);
            n=scanner.nextInt();
            m=scanner.nextInt();
            flag=new boolean[n+5][m+5];
            a=new char[n+5][m+5];
            for (int i = 1; i <=n ; i++) {
        
                String s=scanner.next();
                for (int j = 1; j <=m ; j++) {
        
                    a[i][j]=s.charAt(j-1);
                }
            }
            bfs(1,1);
        }
    }

import java.util.ArrayList;
    import java.util.Scanner;
    
    public class Main {
        
        
        public final static int[][] move = {
        {
        -1, 0},{
        1,0},{
        0,-1},{
        0,1}};//分别表示向上、下、左、右移动一步
        public final static String[] onePath = {
        "U","D","L","R"};//分别表示向上、下、左、右行走
        
        static class point {
           //内部类，用于表示当前行走到达点信息
            public int x;  //当前到达位置横坐标
            public int y;  //当前到达位置纵坐标
            public int step;   //行走到当前顶点所用总步数
            public String path;   //行走到当前顶点的具体路径
            
            point(int x, int y, int step, String path) {
        
                this.x = x;
                this.y = y;
                this.step = step;
                this.path = path;
            }
        }
            
        //判断当前位置是否是可行走的位置，如不能返回false，否则返回true
        public boolean check(int[][] matrix, point a) {
        
            int n = matrix.length - 1, m = matrix[0].length - 1;
            if(a.x < 1 || a.x > n || a.y < 1 || a.y > m || matrix[a.x][a.y] == 1)
                return false;
            return true;
        }
        
        //依据字典序{D,L,R,U}，比较字符串A和B的大小，如果A > B返回true，否则返回false(PS:两者字符个数相同)
        public boolean judge(String A, String B) {
        
            char[] arrayA = A.toCharArray();
            char[] arrayB = B.toCharArray();
            for(int i = 0, len = A.length();i < len;i++) {
        
                if(arrayA[i] < arrayB[i])
                    return false;
            }
            return true;
        }
        //把输入数据，变换为矩阵
        public int[][] getMatrix(String[] A, int m) {
        
            int[][] matrix = new int[A.length + 1][m + 1];
            for(int i = 0;i < A.length;i++) {
        
                char[] arrayA = A[i].toCharArray();
                for(int j = 0;j < m;j++)
                    matrix[i + 1][j + 1] = arrayA[j] - '0';
            }
            return matrix;
        }
        
        public void bfs(String[] A, int m) {
        
            int[][] matrix = getMatrix(A, m);
            ArrayList<point> list = new ArrayList<point>();
            list.add(new point(1,1,0,""));   //表示从顶点(1,1)出发
            int minStep = Integer.MAX_VALUE;  //用于记录到达最终顶点所需最少步数
            String minPath = "";         //用于记录到达最终顶点路径的最小字典序序列
            while(list.size() != 0) {
        
                point begin = list.get(0);  //获取链表第一个顶点，开始进行bfs遍历
                list.remove(0);  //删除进行遍历的起始点
                
                if(begin.x == matrix.length - 1 && begin.y == matrix[0].length - 1) {
          //当该顶点为终点时
                    if(minStep > begin.step) {
        
                        minStep = begin.step;
                        minPath = begin.path;
                    } else if(minStep == begin.step) {
         
                        if(judge(minPath, begin.path))  //当minPath字典序大于begin.step时
                            minPath = begin.path;
                    }
                    continue;   //此处已经是终点，不需要进行下面bfs遍历
                }
                
                for(int i = 0;i < 4;i++) {
          //如果未达到最终顶点(n, m)，进行bfs遍历(分别向上、下、左、右移动)
                    int x = begin.x + move[i][0];
                    int y = begin.y + move[i][1];
                    int step = begin.step + 1;
                    String path = begin.path + onePath[i] ;
                    point temp = new point(x, y, step, path);
                    if(check(matrix, temp)) {
          //当顶点temp是可到达的顶点时
                        list.add(temp);
                        matrix[x][y] = 1;  //到达该顶点后，标记该顶点不可到达，此处奥秘是大大减少了检索次数（如果换成其父母顶点不可到达，则会运行超时）
                    }
                }
            }
            //输出最终结果
            System.out.println(minStep+"\n"+minPath);
            return;
        }
        
        public static void main(String[] args) {
        
            Main test = new Main();
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int m = in.nextInt();
            in.nextLine();  //此处特别注意，输入完整数，下面接着输出字符串，此处处理换行操作
            String[] A = new String[n];
            for(int i = 0;i < n;i++)
                A[i] = in.nextLine();
            test.bfs(A, m);
        }
    }