google 扫地机器人

bagelbagel 发表于 2018-3-9 09:02
这题不是17年年初就有

这应该就是最早出现的时间，哈哈

siy 发表于 2018-3-10 02:48
差不多。但是api给的是顺时针转逆时针转。所以四个if里面应该是转0次1次2次3次。然后cannot move的点是房 ...

在dfs当前层，假如机器人朝向north，那么上左下右4个方向，在进入下一层递归之前，也要调整机器人方向，使其始终朝向north？ 比如moveLeft，就是turn left(1), move one step, turn right(1)，机器人还是朝向north？

rhwfyf 发表于 2018-3-10 13:28
在dfs当前层，假如机器人朝向north，那么上左下右4个方向，在进入下一层递归之前，也要调整机器人方向， ...

不需要。下一层helper时机器人的方向无所谓。但是无路可走时需要返回上一步的位置和方向。比如说现在在原点。现在执行这层helper的第（1/2/3/4）次loop。需要turn（0/1/2/3次）再move。现在在新点。从这个点再执行helper。发现无路可走就需要回到原点。因为你原点的helper要执行forloop四次。有可能没执行完全部四次。这就需要控制机器人回到原点并朝向刚来原点时候的方向。这样再执行下一个loop的时候turn的次数才和loop数相关。

rhwfyf 发表于 2018-3-10 01:09
差不多是这个意思？

void dfs(x, y, back_direction) {

如果是if(visited(x,y)), 那接下来执行的应该是move(back_direciton)再return吧，毕竟move如果true的话那机器人已经移动到那个位置了。

siy 发表于 2018-3-11 11:30
不需要。下一层helper时机器人的方向无所谓。但是无路可走时需要返回上一步的位置和方向。比如说现在在原 ...

请问为什么下一层helper的时候不需要确定方向呢……如果机器人面向东边，和机器人面向西边的记录visited方式应该不一样吧……

siy 发表于 2018-3-9 09:28
我面试的时候小哥说我是他面过的第一个把这道题题和followup都做完的candidate。难点在于一是包了api进去要 ...

请问参数化这个房间指什么

这题的意思不是很清楚，最后是要求什么，是求怎么走最短，还是只要把地都扫了就行了？

我们已经有的API是哪写啊？
turn //顺时针逆时针转
move(direction)
clean

turn 和 move 都需要我们再具体实现吗？
还有direction类是怎么表示的

1. #include <iostream>
   
2. #include <vector>
   
3. #include <unordered_set>
   
4. using namespace std;
   
5. 
   
6. class Robot{
   
7.         private:
   
8.                 vector<vector<int>> data;
   
9.                 int x;
   
10.                 int y;
    
11.                 int N;
    
12.                 int d;//direction
    
13. 
    
14.         public:
    
15. 
    
16.                 bool move(int direction){
    
17.                         int x = direction - d;
    
18.                         if(x > 0){
    
19.                                 turnR(x);
    
20.                         }else if(x < 0){
    
21.                                 turnL(-x);
    
22.                         }
    
23.                         int ret = move();
    
24.                         if(ret)
    
25.                                 cout << "move:" << direction << endl;
    
26.                         return ret;
    
27.                 }
    
28. 
    
29.                 bool move(){
    
30.                         int dx = 0;
    
31.                         int dy = 0;
    
32.                         switch(d){
    
33.                                 case 0:
    
34.                                         dx --;
    
35.                                         break;
    
36.                                 case 1:
    
37.                                         dy ++;
    
38.                                         break;
    
39.                                 case 2:
    
40.                                         dx ++;
    
41.                                         break;
    
42.                                 case 3:
    
43.                                         dy --;
    
44.                                         break;
    
45.                                 default:
    
46.                                         break;
    
47.                         }
    
48.                         int tx = x + dx;
    
49.                         int ty = y + dy;
    
50.                         if( tx >= N || tx < 0 || ty >= N || ty < 0){
    
51.                                 return false;
    
52.                         }
    
53.                         if(data[tx][ty]) return false;
    
54.                         x = tx;
    
55.                         y = ty;
    
56.                         return true;
    
57.                 }
    
58. 
    
59.                 void turnL(int k){
    
60.                         d -= k;
    
61.                         if(d < 0){
    
62.                                 d = -d;
    
63.                                 d = d % 4;
    
64.                                 d = 4 - d;
    
65.                         }
    
66.                 }
    
67. 
    
68.                 void turnR(int k){
    
69.                         d += k;
    
70.                         d = d % 4;
    
71.                 }
    
72. 
    
73. 
    
74.                 void clean(){
    
75.                         cout << "clean:" << x << ":" << y << endl;
    
76.                 }
    
77. 
    
78.                 Robot(){
    
79.                         N = 4;
    
80.                         data = {
    
81.                                 {0,0,0,1},
    
82.                                 {0,1,0,0},
    
83.                                 {0,0,1,1},
    
84.                                 {0,0,0,0}
    
85.                         };
    
86.                         x = 0;
    
87.                         y = 0;
    
88.                         d = 0;
    
89.                 }
    
90. 
    
91.                 void cleanAll(){
    
92.                         unordered_set<int> vis;
    
93.                         help(vis);
    
94.                 }
    
95. 
    
96.                 void help(unordered_set<int> & vis){
    
97.                         if(vis.find(x * N + y) != vis.end()) return;
    
98.                         clean();
    
99.                         vis.insert(x * N + y);
    
100.                         int back[4] = {2, 3, 0, 1};
     
101.                         int dx[4] = {-1,0, 1, 0};
     
102.                         int dy[4] = {0,1, 0, -1};
     
103.                         for(int i = 0; i < 4; i ++){
     
104.                                 int tx = x + dx[i];
     
105.                                 int ty = y + dy[i];
     
106.                                 if( tx >= N || tx < 0 || ty >= N || ty < 0)continue;
     
107.                                 if(vis.find(tx * N + ty) != vis.end()) continue;
     
108.                                 bool ret = move(i);
     
109.                                 if(ret) {
     
110.                                         help(vis);
     
111.                                         move(back[i]);
     
112.                                 }
     
113.                         }
     
114.                 }
     
115. 
     
116. };
     
117. 
     
118. int main() {
     
119.         Robot r;
     .--
120.         r.cleanAll();
     
121.         return 0;
     
122. }
     

复制代码

hululei 发表于 2018-3-19 15:03
这题的意思不是很清楚，最后是要求什么，是求怎么走最短，还是只要把地都扫了就行了？

我们已经有的API ...

要求就是把地都扫完。
move, turnLeft, turnRight, clean可以认为是提供的API，不需要自己实现。

rhwfyf 发表于 2018-3-20 13:14
要求就是把地都扫完。
move, turnLeft, turnRight, clean可以认为是提供的API，不需要自己实现。

为啥人家的代码里move 和turn 都是要实现的