骨骼VO 面经

第四题竟然还有人考。。。好像2-3年前的高频了吧

有谁能讲一下第四题生成迷宫的code或者李扣上的类似题目么？？谢谢！！！

Katherineaa1223 发表于 2021-6-19 13:45
有谁能讲一下第四题生成迷宫的code或者李扣上的类似题目么？？谢谢！！！

[i]

1. int[][] DIR = new int[][] {
   
2.         {-1, 0},
   
3.         {0, 1},
   
4.         {0, -1},
   
5.         {1, 0}
   
6. };       
   
7. public int[][] mazeGenerator(int height, int width, int[] start, int[] end) {
   
8.         int[][] maze = new int[height][width];
   
9.         List<int[]> path = new ArrayList<>();
   
10.         dfs(start[0], start[1], end, visited, path);
    
11.         Random random = new Random();
    
12.         for(int[] point : path) {
    
13.                 maze[point[0]][point[1]] = 1;
    
14.         }
    
15.         for(int i = 0; i < height; ++i) {
    
16.                 for(int j = 0; j < width; ++j) {
    
17.                         if(maze[i][j] == 1) continue;
    
18.                         maze[i][j] = random.nextInt(2);
    
19.                 }
    
20.         }
    
21.         return maze;
    
22. }
    
23. 
    
24. private boolean dfs(int h, int w, int[] end, boolean[][] visited, List<int[]> path) {
    
25.         if(h < 0 || h == visited.length || w < 0 || w == visited[0].length || visited[h][w]) return false;
    
26.         visited[h][w] = true;
    
27.         path.add(new int[]{h, w});
    
28.         if(h == end[0] && w == end[1]) return true;
    
29.         for(int[] dir : DIR) {
    
30.                 if(dfs(maze, h + dir[0], w + dir[1], end, visited, path)) return true;
    
31.         }
    
32.         visited[h][w] = false;
    
33.         path.remove(path.size() - 1);
    
34.         return false;
    
35. }
    
36. 
    
37. /*
    
38.         Followup:
    
39.         其实就是每次把dfs内部用来存放移动方向的DIR在每次call dfs的时候shuffle下.
    
40.         具体实现随意.
    
41. */

复制代码

[/i]

很有用的信息，感谢你的分享！

答的都很好，想不通挂在哪里？

匿名用户 发表于 2021-08-18 07:52:49
答的都很好，想不通挂在哪里？

不知啊…
但是手上别的pkg都比看到的狗L4大……
（微笑）