原创
import java.util.*; public class Main { static int n; //行 static int m; //列 static char maze[][]; //迷宫 static int que_x[]; //横坐标 static int que_y[]; //纵坐标 static char udlr[][]; static int book[][]; //标记 static int dir[][]= { {1,0},{0,-1},{0,1},{-1,0} }; //方向数组DLRU static int step[][]; //存储步数 static int result_step; static int flag=0; static int head=0; //头指针 static int tail=0; //尾指针 static char way[]; //存储路径 static char d_way[]; //中转路径 static void judge_dir(int dx,int dy) { //判断上一步到这一步需要向哪个方向走 //右 if(dx-que_x[head]==0 && dy-que_y[head]==1) { udlr[dx][dy]=‘R‘; } //左 if(dx-que_x[head]==0 && dy-que_y[head]==-1) { udlr[dx][dy]=‘L‘; } //上 if(dx-que_x[head]==-1 && dy-que_y[head]==0) { udlr[dx][dy]=‘U‘; } //下 if(dx-que_x[head]==1 && dy-que_y[head]==0) { udlr[dx][dy]=‘D‘; } } static void find_way(int dx,int dy,int count) { //寻找路径 if(dx==0 && dy==0) { //数组逆序存放于dd_way for(int i=0;i<way.length;i++) { way[i]=d_way[ d_way.length-(i+1) ]; } return; } d_way[count]=udlr[dx][dy]; if(d_way[count]==‘U‘) { //上 find_way(dx+1,dy,count+1); } if(d_way[count]==‘R‘) { //右 find_way(dx,dy-1,count+1); } if(d_way[count]==‘D‘) { //下 find_way(dx-1,dy,count+1); } if(d_way[count]==‘L‘) { //左 find_way(dx,dy+1,count+1); } } public static void main(String[] args) { Scanner reader=new Scanner(System.in); n=reader.nextInt(); m=reader.nextInt(); maze=new char[n][m]; //编号从0开始 udlr=new char[n][m]; //记录四个方向 book=new int[n][m]; step=new int[n][m]; que_x=new int[n*m]; que_y=new int[n*m]; //迷宫赋值 for(int i=0;i<n;i++) { String ss=reader.next(); maze[i]=ss.toCharArray(); } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { book[i][j]=0; step[i][j]=0; } } book[0][0]=1; //起点 //初始位置入队列 que_x[tail]=0; que_y[tail]=0; tail++; while(head<tail) { for(int i=0;i<4;i++) { int dx=que_x[head]+dir[i][0]; int dy=que_y[head]+dir[i][1]; if(dx<0 || dx>n-1 || dy<0 || dy>m-1) { //越界判断 continue; } if(maze[dx][dy]==‘0‘ && book[dx][dy]==0) { //入队列 que_x[tail]=dx; que_y[tail]=dy; book[dx][dy]=1; tail++; //计算步数 step[dx][dy]=step[ que_x[head] ][ que_y[head] ]+1; //存储方向信息 judge_dir(dx,dy); } //判断终点 if(dx==n-1 && dy==m-1) { //先到步数肯定最少，直接存储结果 result_step=step[dx][dy]; //开辟存放路径空间 way=new char[result_step]; d_way=new char[result_step]; find_way(dx,dy,0); flag=1; } } if(flag==1) { break; } head++; } System.out.println(step[n-1][m-1]); for(int i=0;i<result_step;i++) { System.out.print(way[i]); } } }
DFS(超时)
import java.util.*; public class 学霸的迷宫dfs { static int n; static int m; static char maze[][]; //迷宫 static int book[][]; //标记 static int dir[][]= { {1,0},{0,-1},{0,1},{-1,0} }; //方向 static int min_step=999999999; //最小步数 static char way[][]; //存储方向 static char result_way[]; //存储路径 static char d_way[]; //中转路径 static void find_way(int x,int y,int count) { //倒退寻找路径 //所有路径的首结点为(0,0) if(x==0 && y==0) { return; } d_way[count]=way[x][y]; if(way[x][y]==‘R‘) { //右 find_way(x,y-1,count+1); } if(way[x][y]==‘D‘) { //下 find_way(x-1,y,count+1); } if(way[x][y]==‘L‘) { //左 find_way(x,y+1,count+1); } if(way[x][y]==‘U‘) { //上 find_way(x+1,y,count+1); } } static void dfs(int x,int y,int step) { //step代表步数 //步数超越 if(step>min_step) { return; } //出口判断 if(x==n-1 && y==m-1) { if(step<min_step) { min_step=step; //更新步数 //存储路径 find_way(x,y,0); //结果存储 for(int i=0;i<min_step;i++) { result_way[i]=d_way[ min_step-(i+1) ]; } } } for(int i=0;i<4;i++) { int dx=x+dir[i][0]; int dy=y+dir[i][1]; //越界判断 if(dx<0 || dx>n-1 || dy<0 || dy>m-1) { continue; } //障碍点和访问判断 if(maze[dx][dy]==‘1‘ || book[dx][dy]==1) { continue; } //(x,y)到(dx,dy)的方向判断 if(i==0) { way[dx][dy]=‘D‘; } if(i==1) { way[dx][dy]=‘L‘; } if(i==2) { way[dx][dy]=‘R‘; } if(i==3) { way[dx][dy]=‘U‘; } book[dx][dy]=1; dfs(dx,dy,step+1); book[dx][dy]=0; //回溯 } } public static void main(String[] args) { Scanner reader=new Scanner(System.in); n=reader.nextInt(); m=reader.nextInt(); maze=new char[n][m]; book=new int[n][m]; way=new char[n][m]; result_way=new char[n*m]; d_way=new char[n*m]; for(int i=0;i<n;i++) { String ss=reader.next(); maze[i]=ss.toCharArray(); } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { book[i][j]=0; } } book[0][0]=1; dfs(0,0,0); //起点(0,0) System.out.println(min_step); for(int i=0;i<min_step;i++) { System.out.print(result_way[i]); } } }
14:01:10
2018-08-02
原文：https://www.cnblogs.com/chiweiming/p/9406530.html