Facebook 2015暑期实习面经

yuxrose 发表于 2015-4-8 04:03
不是很理解题意。。。是说所有W到所有G的距离？有很多Gate的话，算哪个距离

是“_”到G的距离。每一个“_”到G的距离，W是不能经过的，有一点像迷宫。

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

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

marthew777 发表于 2015-4-8 04:29
大概是这个意思，其实很简单达！

private enum BLOCK {G, W, O};

请问dfs为什么不行?我用dfs实现了，方便的话帮我看下

1. public List<Integer> pathToGates(char[][] maze) {
   
2.                 ArrayList<Integer> res = new ArrayList<Integer>();
   
3.                 if (maze.length == 0 && maze[0].length == 0) {
   
4.                         return res;
   
5.                 }
   
6.                 int[][] visit = new int[maze.length][maze[0].length];
   
7.                 for (int i = 0; i < maze.length; i++) {
   
8.                         for (int j = 0; j < maze[0].length; j++) {
   
9.                                 help(maze, i, j, res, 0 , visit);
   
10.                         }
    
11.                        
    
12.                 }
    
13.                
    
14.                 return res;
    
15.         }
    
16.        
    
17.         public void        help(char[][] maze , int i , int j , ArrayList<Integer> res, int count, int[][] visit) {
    
18.                 if (i < 0 || i >= maze.length || j < 0 || j >= maze[0].length ||visit[i][j] == 1 || maze[i][j] == 'W') {
    
19.                        
    
20.                         return;
    
21.                 }else if (maze[i][j] == 'G') {
    
22.                         res.add(count);
    
23.                        
    
24.                         return;
    
25.                 }
    
26.                 visit[i][j] = 1;
    
27.                 count++;
    
28.                 help(maze, i+1, j, res, count,visit);
    
29.                 help(maze, i-1, j, res, count,visit);
    
30.                 help(maze, i, j+1, res, count,visit);
    
31.                 help(maze, i, j-1, res, count,visit);
    
32.                 visit[i][j] = 0;
    
33.                 count--;
    
34.         }
    
35.        
    
36.         public static void main(String[] args) {
    
37.                
    
38.                
    
39.                 rotate rr = new rotate();
    
40.                 char[][] maze = new char[4][4];
    
41.                 maze[0][0] = '_';
    
42.                 maze[0][1] = 'W';
    
43.                 maze[0][2] = 'G';
    
44.                 maze[0][3] = '_';
    
45.                 maze[1][0] = '_';
    
46.                 maze[1][1] = '_';
    
47.                 maze[1][2] = '_';
    
48.                 maze[1][3] = 'W';
    
49.                 maze[2][0] = '_';
    
50.                 maze[2][1] = 'W';
    
51.                 maze[2][2] = '_';
    
52.                 maze[2][3] = 'W';
    
53.                 maze[3][0] = 'G';
    
54.                 maze[3][1] = 'W';
    
55.                 maze[3][2] = '_';
    
56.                 maze[3][3] = '_';
    
57.                
    
58.                 System.err.println(rr.pathToGates(maze));
    
59.                
    
60.                
    
61.         }

复制代码

haungge0385 发表于 2015-4-8 21:15
请问dfs为什么不行?我用dfs实现了，方便的话帮我看下

要求是找到最短的距离，显然是BFS啊。。

楼主和我的题目一模一样。。

chm34 发表于 2015-4-8 22:24
楼主和我的题目一模一样。。

是什么时候面的？是Facebook吗？

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

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

marthew777 发表于 2015-4-8 04:29
大概是这个意思，其实很简单达！

private enum BLOCK {G, W, O};

哥，你这代码有问题呀，略坑...

您好！
本帖隐藏的内容需要积分高于 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