蓝桥杯算法提高VIP-学霸的迷宫-题解（Java代码）

解题思路:

思路与迷宫问题相同，迷宫问题题解 ,宽度搜索。

有两点不同：

1，getDir()方法，根据向四个方向的移动，得到对应的字符。

2，int next[][]={{1,0},{0,-1},{0,1},{-1,0}};//下一步 ,D L R U 

     根据题目要求 如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。所以next的顺序也应当做些改变。

注意事项:

参考代码:

import java.awt.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
    public static class Q{
        int x;
        int y;
        int dept;//当前步数
        String track;//路线
    }
    
  //根据i的值，返回RDLU;
	 public static String getDir(int i){
		if (i==0) {
			return "D";
		}
		if (i==1) {
			return "L";
		}
		if (i==2) {
			return "R";
		}
		if (i==3) {
			return "U";
		}
		return "error";
	 }
    
    public static void main(String[] args) {
        //队列，queue，先进先出
            //在java中，LinkedList实现 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。
            //所以本题用LinkedList代替Queue。
        //bfs.广度优先搜索，层层递进
        //使用队列存储起点，        
        //遍历四个方向，如果新方向可以走
            //则将新方向存储到队列
        //当四个方向遍历完成后，将首个出列 poll()，并得到首列的元素。重复上一步，即向四个方向遍历。
        //假如遍历到某个点时，刚好是终点，那么结束循环，这就是结果。
        Scanner sc=new Scanner(System.in);
        int next[][]={{1,0},{0,-1},{0,1},{-1,0}};//下一步 ,D L R U
            int n=sc.nextInt();
            int m=sc.nextInt();
            int sx=0,sy=0;//起点坐标
            int gx=n-1,gy=m-1;//终点坐标
            LinkedList<Q> que=new LinkedList<Main.Q>();
            char arr[][]=new char[n][m];
            int flag[][]=new int[n][m];//标记是否走过
             
            //输入
            for (int i = 0; i < n; i++) {
                String str=sc.next();
                for (int j = 0; j <str.length(); j++) {
                    arr[i][j]=str.charAt(j);
                }
            }
            //开始广搜
            flag[sx][sy]=1;//标记开始坐标
            Q q=new Q();//初始化开始坐标
            q.x=sx;
            q.y=sy;
            q.dept=0;
            q.track="";
            que.add(q);//添加
            int result=0;//结果步数
            String resultSract="";//结果路线
            while (que.size()!=0) {
                Q first=que.poll();//取出头列，并删除
                if (first.x==gx && first.y==gy) {
                	result=first.dept;//改变步数
//                	if (result==first.dept) {//如果步数相等
//						if (resultSract.compareTo(first.track)>0) {//按结果的字典比较
			                 resultSract=first.track;
//						}
//					}
                }
                
                for (int i = 0; i <4; i++) {//右下左上 4 个步骤
                    //如果已经到达终点，那么退出循环，并且得到结果
                    int tx=first.x+next[i][0];
                    int ty=first.y+next[i][1];
                    if (tx>=0 && tx<n && ty>=0 && ty<m 
                        && arr[tx][ty]!='1' && flag[tx][ty]==0) {//符合条件
                        flag[tx][ty]=1;//标记走过
                        Q temp=new Q();
                        temp.x=tx;
                        temp.y=ty;
                        temp.dept=first.dept+1;
                        temp.track=first.track+getDir(i);
                        que.add(temp);//添加一个坐标到队列
                    }
                }
            }
            //输出结果
            if (result==0) {
                System.out.println("-1");
            }else {
                System.out.println(result);
                System.out.println(resultSract);
            }
        
        
         
}
   
}