题目描述：
下图给出了一个迷宫的平面图，其中标记为1的是障碍，0的是可以通行的地方
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。
对于下面这个更复杂的迷宫(30 行 50 列)，请找出一种通过迷宫的方式， 其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。 请注意在字典序中D<L<R<U。
解题思路：
> 本题是典型的迷宫问题，可以利用bfs（广度优先遍历） > 也可以用dfs进行搜索路径，但最终要字典序最小，所以dfs不太容易操作 > 广搜的顺义要以D-L-R-U进行，因为要字典序最小 > 这点可以利用4次循环即可 > 怎么判断是最小路径呢？ > 因为是广搜，要一层一层的搜 > 所以当前节点探寻了每个和它相邻的节点 > 一但到达终点即退出，最小路径为探索的层数，这点和深搜不太相同， > dfs是不断进行递归回溯，进行比较找最小值 > 而bfs可以利用自身优势确定最小值
代码：
public class Main { public static int dir[][] = new int[][] {{1,0},{0,-1},{0,1},{-1,0}}; public static char direction[] = new char[] {'D','L','R','U'}; public static int[][] map=new int[30][50]; public static boolean[][] visit=new boolean[30][50]; public static void main(String[] args){ Scanner sc=new Scanner(System.in); for(int i=0;i<30;i++) { String s=sc.next(); for(int j=0;j<50;j++) { map[i][j]=s.charAt(j)-'0'; } } bfs(new Point(0, 0)); } public static void bfs(Point start) { Queue<Point> q=new LinkedList<Point>(); q.add(start); visit[start.i][start.j]=true; while(!q.isEmpty()) { Point p=q.peek(); if(p.i==29&&p.j==49) { System.out.println(p.step); System.out.println(p.way); return; } for(int i=0;i<4;i++) { int new_i=p.i+dir[i][0]; int new_j=p.j+dir[i][1]; Point temp=new Point(new_i,new_j); if(new_i>=0&&new_j>=0&&new_i<30&&new_j<50&&!visit[new_i][new_j]&&map[new_i][new_j]!=1) { visit[new_i][new_j]=true; temp.step=p.step+1; temp.way=p.way+direction[i]; q.add(temp); } } q.poll(); } } } class Point{ int i; int j; int step; String way; public Point() { i=j=step=0; way=""; } public Point(int i,int j) { this.i=i; this.j=j; step=0; way=""; } }
答案：
（最少一共186步） DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
