考点

1、BFS求最短路径的长度

2、枚举求出路径走法（注意枚举过程中要按照字典序最小的方案来求）

题目描述

下图给出了一个迷宫的平面图，其中标记为1 的为障碍，标记为0 的为可 以通行的地方。

010000

110000

迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。 对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫， 一共10 步。其中D、U、L、R 分别表示向下、向上、向左、向右走。

对于下面这个更复杂的迷宫（30 行50 列），请找出一种通过迷宫的方式， 其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。 请注意在字典序中D<L<R<U。

01010101001011001001010110010110100100001000101010


00011111000000101000010010100010100000101100000000


00111000001010100001100010000001000101001100001001


00000010000000101011001111010001100000101010100011


10101001000000010100100001000100000100011110101001


10100101000101000000001110110010110101101010100001


11010000001001110111001001000011101001011011101000


00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个字符串，包含四种字母D、U、L、R，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

思路

这里用的是bfs而不是dfs（求最短路径）

广搜可以搜出来最短路径，但深搜是搜不出来的！

先将距离为1的点求出来，再将距离为2的点、为3的点……求出来，当它第一次求出终点时，就是最短路径

这里要求字典序最小，那么我们就要倒着搜（因为我们要知道序列）

bfs搜的时候不需要保存路径，倒着做完一遍之后，求出每个点到终点的最短距离，然后再正着做一遍。

怎么判断是不是最短路径？

只要每次选择的路到终点的最短路径比上一个结点到终点的最短路径少1（一步一步走的）

也就是

dis[x][y] == 1 + dis[newx][newy]

代码

 1 import java.util.LinkedList;
 2 import java.util.Queue;
 3 import java.util.Scanner;
 4 
 5 public class Main {
 6     static int n = 30, m = 50;
 7     static int[][] dis = new int[n][m];// 记录每个点到终点的最短路径
 8     static char[][] biao = new char[n][m];// 记录迷宫
 9     static Queue<int[]> queue = new LinkedList<>();// 利用linkedlist实现队列
10     // 按照字典序列设置方向，DLRU，这样在枚举的时候比较方便
11     static int[] dx = new int[] { 1, 0, 0, -1 };
12     static int[] dy = new int[] { 0, -1, 1, 0 };
13     static char[] dir = new char[] { 'D', 'L', 'R', 'U' };
14 
15     public static void main(String args[]) {
16         Scanner in = new Scanner(System.in);
17         for (int i = 0; i < n; i++) {
18             String s = in.next();
19             biao[i] = s.toCharArray();
20         }
21         // 初始化所有距离
22         clean();
23         // 倒着使用bfs
24         bfs();
25         System.out.println("min distance = " + dis[0][0]); // 测试一下从起点到终点的最短路径长度（186）
26 
27         // 接下来开始枚举，也就是再正着走一遍（记录路径）
28         int x = 0, y = 0;
29         StringBuffer ans = new StringBuffer();
30         // while里面应该是或者的关系而不是并且的关系
31         // 因为最终要x和y都走到终点，x和y只要有一个没有到达终点，就要继续走，
32         // 如果错用了并且，那么意思是只要x和y有一个到达了最后一行/列，就停止，算出来是185长度的错误答案
33         while (x != n - 1 || y != m - 1) {
34             for (int i = 0; i < 4; i++) {
35                 int newx = x + dx[i];
36                 int newy = y + dy[i];
37                 // 判断这个新点是否合法
38                 if (newx >= 0 && newx < n && newy >= 0 && newy < m && biao[newx][newy] == '0') {
39                     // 判断这个新点是否存在一条最短路径到终点
40                     if (dis[x][y] == 1 + dis[newx][newy]) {
41                         x = newx;// 更新x
42                         y = newy;// 更新y
43                         ans.append(dir[i]);// 更新路径
44                         // 这里不再需要break，因为我们一定是沿着合法路径走的
45                     }
46 
47                 }
48             }
49         }
50         System.out.println(ans.toString());
51     }
52 
53     public static void clean() {
54         for (int i = 0; i < n; i++) {
55             for (int j = 0; j < m; j++)
56                 dis[i][j] = -1;
57         }
58     }
59 
60     public static void bfs() {
61         queue.add(new int[] { n - 1, m - 1 });
62         dis[n - 1][m - 1] = 0;// 终点到终点的距离为0
63         while (!queue.isEmpty()) {
64             int[] temp = queue.poll();
65             for (int i = 0; i < 4; i++) { // 对4个方向
66                 // 得到新的点的坐标
67                 int x = temp[0] + dx[i];
68                 int y = temp[1] + dy[i];
69                 // 如果这个点合法且没有被访问过且没有障碍物，我们才会去更新它
70                 if (x >= 0 && x < n && y >= 0 && y < m && dis[x][y] == -1 && biao[x][y] == '0') {
71                     // 距离更新为上一个点的最短距离+1
72                     dis[x][y] = dis[temp[0]][temp[1]] + 1;
73                     queue.add(new int[] { x, y });
74                 }
75             }
76         }
77     }
78 }

答案

输出结果：

1 min distance = 186
2 DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDRDRRURRUURRDDDDRDRRRRRURRRDRRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR