亲宝软件园·资讯

展开

阿里笔试题(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 }
View Code

代码参考自这篇博客,原来的代码在每次取出队列最前端的点后判断是不是出口。但是似乎这样会增加一些不必要的计算(自己的想法,不知道合不合理),例如在某一点,其上下左右四个点中有一个就是出口点,那么在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

加载全部内容

相关教程
猜你喜欢
用户评论