snapchat电面gg

随便聊聊简历，然后一道题，有墙找路的变形 1 是路 0 是墙，

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

se
没做出来，哪个大神写下分享我看看吧。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

感谢楼主分享，用bfs撸了一遍，函数的参数分别是棋盘，起点的坐标，终点的坐标

1. public class ShortestStep {
   
2.    
   
3.     public int shortestPath(int[][] board, int i, int j, int p, int q) {
   
4.         
   
5.         if (board[i][j] == 0 || board[p][q] == 0) {
   
6.             return -1;
   
7.         }
   
8.         
   
9.         int m = board.length;
   
10.         int n = board[0].length;
    
11.         Queue<Integer> queue = new LinkedList<>();
    
12.         Map<Integer, Integer> map = new HashMap<>();
    
13.         queue.offer(i * n + j);
    
14.         map.put(i * n + j, 0);
    
15.         while (!queue.isEmpty()) {
    
16.             int cur = queue.poll();
    
17.             int step = map.get(cur);
    
18.             int x = cur / n;
    
19.             int y = cur % n;
    
20.             if (x == p && y == q) {
    
21.                 return step;
    
22.             }
    
23.             
    
24.             if (x > 0 && board[x - 1][y] == 1 && !map.containsKey((x - 1) * n + y)) {
    
25.                 map.put((x - 1) * n + y, step + 1);
    
26.                 queue.offer((x - 1) * n + y);
    
27.             }
    
28.             if (x < m - 1 && board[x + 1][y] == 1 && !map.containsKey((x + 1) * n + y)) {
    
29.                 map.put((x + 1) * n + y, step + 1);
    
30.                 queue.offer((x + 1) * n + y);
    
31.             }
    
32.             if (y > 0 && board[x][y - 1] == 1 && !map.containsKey(x * n + y - 1)) {
    
33.                 map.put(x * n + y - 1, step + 1);
    
34.                 queue.offer(x * n + y - 1);
    
35.             }
    
36.             if (y < n - 1 && board[x][y + 1] == 1 && !map.containsKey(x * n + y + 1)) {
    
37.                 map.put(x * n + y + 1, step + 1);
    
38.                 queue.offer(x * n + y + 1);
    
39.             }
    
40.         }
    
41.         return -1;
    
42.     }
    
43.    
    
44.     public static void main(String[] args) {
    
45.         ShortestStep solution = new ShortestStep();
    
46.         int[][] board = {
    
47.                 {1, 0, 1, 1, 1},
    
48.                 {1, 0, 1, 1, 1},
    
49.                 {1, 1, 1, 1, 1},
    
50.                 {0, 1, 0, 0, 1},
    
51.                 {1, 1, 1, 0, 1}};
    
52.         System.out.println(solution.shortestPath(board, 0, 0, 4, 0));
    
53.         
    
54.         int[][] board0 = {
    
55.                 {1, 0, 1, 1, 1},
    
56.                 {1, 0, 1, 0, 1},
    
57.                 {1, 1, 1, 0, 1},
    
58.                 {0, 1, 0, 0, 1},
    
59.                 {1, 1, 1, 0, 1}};
    
60.         System.out.println(solution.shortestPath(board0, 0, 0, 4, 4));
    
61.         
    
62.         int[][] board2 = {
    
63.                 {1, 0, 1, 1, 1},
    
64.                 {1, 0, 1, 1, 1},
    
65.                 {1, 1, 1, 0, 1},
    
66.                 {0, 1, 0, 0, 1},
    
67.                 {1, 1, 1, 0, 1}};
    
68.         System.out.println(solution.shortestPath(board2, 0, 0, 4, 4));
    
69.         
    
70.         int[][] board3 = {
    
71.                 {1, 0, 1, 1, 1},
    
72.                 {1, 0, 1, 0, 1},
    
73.                 {1, 1, 0, 1, 0},
    
74.                 {0, 1, 0, 0, 1},
    
75.                 {1, 1, 1, 0, 1}};
    
76.         System.out.println(solution.shortestPath(board3, 0, 0, 2, 3));
    
77.     }
    
78. 
    
79. }
    

复制代码

感谢楼主分享~ 写了一个求大家指正~

1. import java.util.*;
   
2. 
   
3. class Solution {
   
4.         //1 是路 0 是墙
   
5.         int res = Integer.MAX_VALUE;
   
6.         public int minStep(int[][] matrix){
   
7.                 if(matrix == null || matrix.length == 0) return 0;
   
8.                 int row = matrix.length, col = matrix[0].length;
   
9.                
   
10.                 for(int i = 0; i < row; i++){
    
11.                         dfs(i, 0, matrix);
    
12.                 }
    
13.                 if(res == Integer.MAX_VALUE) return -1;
    
14.                 else return res;
    
15.         }
    
16.        
    
17.         private void dfs(int x, int y, int[][] matrix){
    
18.                 int row = matrix.length, col = matrix[0].length;
    
19.                 int[][] dp = new int[row][col];
    
20.                 for(int i = 0; i < row; i++){
    
21.                         Arrays.fill(dp[i], Integer.MAX_VALUE);
    
22.                 }
    
23.                
    
24.                 boolean[][] visited = new boolean[row][col];
    
25.                 helper(x, y, matrix, dp, visited, 0);
    
26.         }
    
27.        
    
28.         private void helper(int x, int y, int[][] matrix, int[][] dp, boolean[][] visited, int step){
    
29.                 int row = matrix.length, col = matrix[0].length;
    
30.                 if(x < 0 || x >= row || y < 0 || y >= col || matrix[x][y] == 0 || visited[x][y]) return;
    
31.                 if(step >= dp[x][y]) return;
    
32.                
    
33.                 dp[x][y] = step;
    
34.                 visited[x][y] = true;
    
35.                
    
36.                 if(y == col - 1){
    
37.                         res = Math.min(res, dp[x][y]);
    
38.                         visited[x][y] = false;
    
39.                         return;
    
40.                 }
    
41.                
    
42.                 int[] surroundX = {-1, 1, 0, 0};
    
43.                 int[] surroundY = {0, 0, -1, 1};
    
44.                 for(int i = 0; i < 4; i++){
    
45.                         int nx = x + surroundX[i];
    
46.                         int ny = y + surroundY[i];
    
47.                         helper(nx, ny, matrix, dp, visited, dp[x][y] + 1);
    
48.                 }
    
49.                 visited[x][y] = false;
    
50.         }
    
51.        
    
52.        
    
53.         public static void main(String[] args) {
    
54.                 Solution r = new Solution();
    
55.                 int[][] matrix =
    
56.                 {{0,1,1,1,1,0},
    
57.                  {1,1,0,0,1,0},
    
58.                  {1,1,0,1,1,0},
    
59.                  {0,1,0,1,0,0},
    
60.                  {0,1,0,1,1,1}};
    
61.                
    
62.                 int res = r.minStep(matrix);
    
63.                 System.out.println(res);
    
64.         }
    
65. }

复制代码

LZ这个走到方向是四个方向都可以走吗？

我觉得应该就是用Dijkstra找图上两点的最短路径

不就是最基本的BFS的嘛，你可以认为从一个虚拟节点开始搜索，这个节点的邻居就是第一列的所有点

从左边每一个 1 开始， dfs ， 4 个方向都要找， 记录 visit[i,j]， 要剪枝 记录 possible[i,j]

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

lvvvvv 发表于 2016-8-6 11:23
从左边每一个 1 开始， dfs ， 4 个方向都要找， 记录 visit， 要剪枝 记录 possible

既然题目说了是从最左边的任何一点到最右边的任何一点，我想只需要搜索上、下、右三个方向了吧？

ryancooper 发表于 2016-8-6 10:51
不就是最基本的BFS的嘛，你可以认为从一个虚拟节点开始搜索，这个节点的邻居就是第一列的所有点

如果使用BFS的话，那还需要加另外一个二维数组记录是否访问过么？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies