阿里笔试题(3.23)——走迷宫
旺仔真知棒 人气:0时间原因没参加23号的笔试，之后看了一下笔试题，第一道纯计算，主要是找到数学规律，另外注意中间取模防止溢出。第二道看了之后感觉有点头秃，还是自己平时刷题太少。。。。。网上看了看其他大佬的解法然后自己写了一下，这里总结一下。
题目如下：
给一个迷宫(1<=n,m<=500), 小明要从初始位置S到达目标位置E，支持五种操作，上/下/左/右/瞬移，瞬移一共可以用5次，每次可以从(x,y) 移动到(n-1-x, m-1-y)， 问小明从S到E的最短时间，如果不能到达输出-1。
示例：
输入：
4 4 #S.. E#.. .... ....输出：
4
解释：
首先从S(0,1)瞬移到(3,2)，再网上一步(2,2)，再往右一步(2,3)，最后瞬移到达E(1,0)，共4步。
1. 不考虑瞬移操作
如果不考虑瞬移操作，就是一般的迷宫最短路径题，用BFS搜索即可，并且BFS能够保证找到的第一个解就是最优解。解法如下：
1 import java.util.LinkedList;
2 import java.util.Queue;
3 import java.util.Scanner;
4
5 public class Main{
6 public static void main(String[] args){
7 Scanner sc = new Scanner(System.in);
8 while(sc.hasNext()){
9 int n = sc.nextInt();
10 int m = sc.nextInt();
11 char[][] migong = new char[n][m];
12 int[] begin = new int[2];
13 int[] end = new int [2];
14 for(int i =0; i < n; i++){
15 String s = sc.next();
16 migong[i] = s.toCharArray();
17 if(s.contains("S")){
18 begin[0] = i;
19 begin[1] = s.indexOf('S');
20 }
21 if(s.contains("G")){
22 end[0] = i;
23 end[1] = s.indexOf('G');
24 }
25 }
26 int shortestPath = getPath(migong, begin, end);
27 System.out.println(shortestPath);
28 }
29 }
30
31 private static int getPath(char[][] migong, int[] begin, int[] end){
32 // 四个移动方向,dx和dy一一对应
33 int[] dx = {1, 0, -1, 0};
34 int[] dy = {0, 1, 0, -1};
35 // path存储当前点到起点的最短路径
36 int[][] path = new int[migong.length][migong[0].length];
37 Queue<int[]> queue = new LinkedList<int[]>();
38 for(int i = 0; i < migong.length; i++){
39 for(int j = 0; j < migong[0].length; j++){
40 path[i][j] = Integer.MAX_VALUE; // 初始化所有点的最短路径为最大值
41 }
42 }
43 queue.offer(begin); // 起始点放入队列
44 path[begin[0]][begin[1]] = 0;
45 // 一直循环直到队列为空或是遍历到出口
46 while(!queue.isEmpty()){
47 int[] curr = queue.poll(); // 取出队列最前端的点
48 // 遍历每一个方向
49 for(int i = 0; i < 4; i++){
50 int x = curr[0] + dx[i];
51 int y = curr[1] + dy[i];
52 // 判断是否可以移动到当前点
53 if(x >= 0 && x < migong.length && y >= 0 && y < migong[0].length && migong[x][y] != '#' && path[x][y] == Integer.MAX_VALUE){
54 path[x][y] = path[curr[0]][curr[1]] + 1; // 可以移动那么当前点的路径长度就是上一步加1
55 if(x == end[0] && y == end[1]){ // 到达出口
56 return path[x][y];
57 }
58 queue.offer(new int[]{x, y}); // 当前点入队
59 }
60 }
61 }
62 return -1; // 队列为空但是还没到达出口，表明无法到达
63 }
64 }
代码参考自这篇博客，原来的代码在每次取出队列最前端的点后判断是不是出口。但是似乎这样会增加一些不必要的计算(自己的想法，不知道合不合理)，例如在某一点，其上下左右四个点中有一个就是出口点，那么在for循环中每次向某个方向移动后就判断是不是出口，这样避免了需要将四个点都入队然后继续计算。
2. 考虑可以瞬移的操作
回到阿里这道笔试题，这个瞬移的操作我想了半天没想明白怎么搞。。。。菜哭。然后看了一下大佬们的解法，自己写了一下：
1 import java.util.LinkedList;
2 import java.util.Queue;
3 import java.util.Scanner;
4
5 public class Main{
6 public static void main(String[] args){
7 Scanner sc = new Scanner(System.in);
8 while(sc.hasNext()){
9 int n = sc.nextInt();
10 int m = sc.nextInt();
11 char[][] migong = new char[n][m];
12 int[] begin = new int[2];
13 int[] end = new int [2];
14 for(int i =0; i < n; i++){
15 String s = sc.next();
16 migong[i] = s.toCharArray();
17 if(s.contains("S")){
18 begin[0] = i;
19 begin[1] = s.indexOf('S');
20 }
21 if(s.contains("G")){
22 end[0] = i;
23 end[1] = s.indexOf('G');
24 }
25 }
26 int shortestPath = getPath(migong, begin, end);
27 System.out.println(shortestPath);
28 }
29 sc.close();
30 }
31
32 private static int getPath(char[][] migong, int[] begin, int[] end){
33 // 四个移动方向,dx和dy一一对应
34 int[] dx = {1, 0, -1, 0};
35 int[] dy = {0, 1, 0, -1};
36 // 用三维数据path存储从起点到某一点的最短路径和飞行次数
37 // 其中path[i][j][0]存储起点到[i][j]的最短路径
38 // path[i][j][1]存储起点到[i][j]的飞行次数
39 int[][][] path = new int[migong.length][migong[0].length][2];
40 Queue<int[]> queue = new LinkedList<int[]>();
41 for(int i = 0; i < migong.length; i++){
42 for(int j = 0; j < migong[0].length; j++){
43 path[i][j][0] = Integer.MAX_VALUE; // 初始化所有点的最短路径为最大值
44 path[i][j][1] = 0; // 初始化所有点的飞行次数为0
45 }
46 }
47 queue.offer(begin); // 起始点放入队列
48 path[begin[0]][begin[1]][0] = 0;
49 // 一直循环直到队列为空或是遍历到出口
50 while(!queue.isEmpty()){
51 int[] curr = queue.poll(); // 取出队列最前端的点
52 if(curr[0] == end[0] && curr[1] == end[1]){ // 到达出口
53 return path[curr[0]][curr[1]][0];
54 }
55
56 // 首先遍历每一个方向，单步移动
57 for(int i = 0; i < 4; i++){
58 int x = curr[0] + dx[i];
59 int y = curr[1] + dy[i];
60 // 判断是否可以移动到当前点
61 if(x >= 0 && x < migong.length && y >= 0 && y < migong[0].length && migong[x][y] != '#' && path[x][y][0] == Integer.MAX_VALUE){
62 path[x][y][0] = path[curr[0]][curr[1]][0] + 1; // 可以移动那么当前点的路径长度就是上一步加1
63 queue.offer(new int[]{x, y}); // 当前点入队
64 }
65 }
66
67 // 如果当前点的飞行次数小于5次，则尝试从当前点飞行到其对称点
68 if(path[curr[0]][curr[1]][1] < 5){
69 // 当前点对称位置坐标
70 int flyX = migong.length - 1 - curr[0];
71 int flyY = migong[0].length - 1 - curr[1];
72 // 判断当前点对称位置是否能到达
73 if(flyX >= 0 && flyX < migong.length && flyY >= 0 && flyY < migong[0].length && migong[flyX][flyY] != '#' && path[flyX][flyY][0] == Integer.MAX_VALUE){
74 path[flyX][flyY][0] = path[curr[0]][curr[1]][0] + 1; // 飞行到对称点，路径长度+1
75 path[flyX][flyY][1] = path[curr[0]][curr[1]][1] + 1; // 到达对称点的飞行次数就是当前点的飞行次数+1
76 queue.offer(new int[]{flyX, flyY}); // 对称点入队
77 }
78 }
79 }
80 return -1; // 队列为空但是还没到达出口，表明无法到达
81 }
82 }
主要是两个变化，首先将原本存储路径的二维数组 path 变成三维数组，第三维的长度为2，其中 path[i][j][0] 存储的就是点ij到出发点的最短距离，即原本的 path[i][j] ， path[i][j][1] 存放到达当前点的瞬移次数；然后就是，每次在向四个方向都移动之后，再找到当前点的对称点，看是不是可以瞬移过去，可以的话就更新其对称点的 path 值。
代码是参考了其他两位大神的，在此表示感谢。因为没机会在刷题平台上测试，只是在自己的测试用例上通过了所以不知道有没有什么问题，欢迎大家批评指正。明天参加阿里的笔试，希望别被虐的太惨，大家都加油啊！
参考资料
1. https://blog.csdn.net/c_yejiajun/articlehttps://img.qb5200.com/download-x/details/86655430
2. https://www.nowcoder.comhttps://img.qb5200.com/download-x/discuss/389778?type=1
3. https://www.cnblogs.com/xlsryj/p/12558114.html
加载全部内容