google 扫地机器人

siy 发表于 2018-3-9 09:24
我面试面了这道题最后过了。我是dfs，用一个set记录visited。设定起点是原点，dfs helper函数要传机器人当 ...

请问大神，follow up是啥？什么思路呢？

flyPacific111 发表于 2018-4-5 06:40
you need a moveBack function in the end? I posted one but not sure it's correct. You can take a lo ...

1. for(int i=0; i<directions.length; i++) {
   
2.          TurnLeft(i);
   
3.          if(Move()) {
   
4.              DFS(myRobot,x + directions[i][0], y + directions[i][1], visited);

复制代码

像这样对吗？

TsengJuiWang 发表于 2018-4-7 09:23
像这样对吗？

代码不见了，哭。。。。就是在move成功之后要TurnLeft(2), Move(), TurnLeft(2)对吗？

TsengJuiWang 发表于 2018-4-7 09:13
为什么move成功之后，调用完DFS没有调用方法把机器人放回到调用前的位置？

假設在當前的DFS層(假設這層DFS的名稱為Lv=1)，機器人位在座標 x=2, y=3 的位置
並且 for loop 現在是 i=1
假設機器人可以往 i=1 的方向前進，也就是說 if(Move()) 是 true
則會調用 DFS(myRobot, x+0, y-1, visited) 進入下一層 DFS (假設這層DFS的名稱為Lv=2)
當Lv=2層的DFS結束後，回到 Lv=1 層的DFS
這時機器人的座標仍然在 x=2, y=3的位置，因為要從Lv=1進入Lv=2之前，我並沒有修改x與y的值
這樣機器人仍然維持在Lv=1層的位置
不知道這樣有沒有問題
麻煩再互相討論一下
謝謝

flyPacific111 发表于 2018-4-5 06:40
you need a moveBack function in the end? I posted one but not sure it's correct. You can take a lo ...

我有看過你的方法，但不懂為甚麼要連續
turnLeft(0)
turnLeft(1)
turnLeft(2)
turnLeft(3)

turnLeft(k)的意思是會向左轉k次
所以不應該是
turnLeft(1)
turnLeft(1)
turnLeft(1)
turnLeft(1)
嗎?

另外，關於DFS結束後的moveBack

假設在當前的DFS層(假設這層DFS的名稱為Lv=1)，機器人位在座標 x=2, y=3 的位置
並且 for loop 現在是 i=1
假設機器人可以往 i=1 的方向前進，也就是說 if(Move()) 是 true
則會調用 DFS(myRobot, x+0, y-1, visited) 進入下一層 DFS (假設這層DFS的名稱為Lv=2)
當Lv=2層的DFS結束後，回到 Lv=1 層的DFS
這時機器人的座標仍然在 x=2, y=3的位置，因為要從Lv=1進入Lv=2之前，我並沒有修改x與y的值
這樣機器人仍然維持在Lv=1層的位置
不知道這樣有沒有問題
麻煩再互相討論一下
謝謝

这题有不用memorization 的解法吗？就是不记录走过的路径的那种

lf963 发表于 2018-4-7 10:54
假設在當前的DFS層(假設這層DFS的名稱為Lv=1)，機器人位在座標 x=2, y=3 的位置
並且 for loop 現在是 i ...

题里面说move成功的话机器人就移到下一个位置了，所以说虽然你没有改记得x和y但是机器人已经跑了，是这样吗，还是我理解错了

lf963 发表于 2018-4-7 11:06
我有看過你的方法，但不懂為甚麼要連續
turnLeft(0)
turnLeft(1)

我记得turnLeft（k）是90*K

TsengJuiWang 发表于 2018-4-7 12:41
题里面说move成功的话机器人就移到下一个位置了，所以说虽然你没有改记得x和y但是机器人已经跑了，是这样 ...

你是正確的！是我搞錯了。下面是我的想法

1. public static void main(String[] args){
   
2.         Robot myRobot = new Robot();
   
3.        
   
4.                                                                                 //3 means face toward north
   
5.         new RobotCleaner().DFS(myRobot, 0, 0, new HashSet<Coordinate>,3);   
   
6. }
   
7.     //faceTo: the position that the robot is now facing toward
   
8.     //faceTo = 0: face toward west
   
9.     //factTo = 1: face toward south
   
10.     //faceTo = 2: face toward east
    
11.     //factTo = 3: face toward north
    
12.        
    
13. void DFS(Robot myRobot, int x, int y, HashSet<Coordinate> visited, int faceTo){
    
14.         if(visited.contains(new Coordinate(x,y)))
    
15.                 return;
    
16.         myRobot.Clean();
    
17.         visited.add(new Coordinate(x, y));
    
18.         int[][] directions = {{-1,0},{0,-1},{1,0},{0,1}};   //west south east north
    
19. 
    
20.         //During each for loop iteration, the robot will turn left 90 degree
    
21.         //so after the for loop finish, the robot will face toward its original direction
    
22.         for(int i=0; i<directions.length; i++){
    
23.                 //faceTo is always between 0 to 3 inclusive
    
24.                 faceTo = (faceTo + 1) % directions.length;
    
25.                
    
26.                 TurnLeft(1);    //turn left 90 degree
    
27.                
    
28.                 if(Move())
    
29.                         DFS(myRobot,x + directions[faceTo][0], y + directions[faceTo][1], visited, faceTo);
    
30.                
    
31.                 else    //if next cell is obstacle or wall, add the next cell to visited
    
32.                         visited.add(new Coordinate(x + directions[faceTo][0], y + directions[faceTo][1]));
    
33.                 moveBack();
    
34.         }
    
35. }
    
36. 
    
37. void moveBack(){
    
38.         TurnLeft(2);
    
39.         Move();
    
40.         TurnLeft(2);
    
41. }
    
42.        
    
43. class Coordinate{
    
44.     int x;
    
45.     int y;
    
46.     Coordinate(int x, int y){
    
47.         this.x = x;
    
48.         this.y = y;
    
49. }
    

复制代码