google 扫地机器人

看了地里对扫地机器人这道题的讨论，零零散散的还是没太搞明白。
这道题挺高频的，地里大牛这么多，大家来讨论讨论这道题具体该怎么做？
谢谢！

Robot Clearner

Givena robot cleaner in a room modeled as a grid. Each cell in the grid can be emptyor blocked. The robot cleaner can move forward, turn left or turn right. Whenit tries to move into a blocked cell, its bumper sensor detects the obstacleand it stays on the current cell.

Thecontrol API:

interfaceRobot {

  //returns true if next cell is open and robot moves into the cell.

  //returns false if next cell is obstacle and robot stays on the current cell.

  booleanMove();

  //Robot will stay on the same cell after calling Turn*. k indicates how

  //many turns to perform.

  voidTurnLeft(int k);

  voidTurnRight(int k);

  //Clean the current cell.

  voidClean();more.

  booleanMove(Direction d);

}

我面试面了这道题最后过了。我是dfs，用一个set记录visited。设定起点是原点，dfs helper函数要传机器人当前方向，用0123表示就可以。每一个helper函数用for循环走四次。每一次按照顺时针或者逆时针转一下。把走过的坐标和cannot move的点都放进visited。最重要的是走完发现无路可走之后要再转向后方走一步再转向后，也就是返回上级helper函数时机器人所在的位置和面朝的方向。

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. 
    . 1point 3acres
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;
    . Waral dи,
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. }
     

复制代码

class robot{
   
. Χ    int[] pos;
.google  и    Set<String> visited;
    Stack<int[]> stack;
    Stack<Integer> actions;

    robot(){
        pos = new int[]{0, 0};
        visited = new HashSet<>();
        stack = new Stack<>();
. 1point 3 acres        stack.push(new int[]{0,0,0});
        actions = new Stack<>();
    }

    private boolean move(){}

    private void turnLeft(){}

    private void turnRight(){}

    private boolean moveF(){
        boolean succ = move();
        if(succ)
            pos[1]++;
        return succ;
    }

    private boolean moveL(){
        turnLeft(1);
        boolean succ = move();
        if(succ)
            pos[0]--;
        turnRight(1);
        return succ;
    }

    private boolean moveR(){
        turnRight(1);
        boolean succ = move();
        if(succ)
            pos[0]++;
        turnLeft(1);
        return succ;
    }

    private boolean moveB(){
        turnLeft(2);
        boolean succ = move();
        if(succ)
            pos[1]--;
        turnRight(2);
        return succ;
    }

    private boolean moveNext(int x){
        if(x == 0) return moveF();
        else if(x == 1) return moveR();
        else if(x == 2) return moveB();
        else if(x == 3) return moveL();
        return false;
    }

    private void Return(int x){
        if(x == 0) moveB();
        else if(x == 1) moveL();
        else if(x == 2) moveF();
        else if(x == 3) moveR();
    }


    private void clean(){}

    private void traverse(){
        while(!stack.isEmpty()){
            int[] cur = stack.peek();
            int x = cur[0], y = cur[1];
            
            if(!visited(posStr(cur[0], cur[1]))){
                visited.add(posStr(cur[0], cur[1]));
                clean();
            }

            String[] nextPoint = new String[]{posStr(cur[0], cur[1]+1),posStr(cur[0]+1, cur[1]),
                        posStr(cur[0], cur[1]-1),posStr(cur[0]-1, cur[1])};

            while(cur[2] < 4 && (visited.contains(nextPoint(cur[2])) || !moveNext(cur[2])))
                cur[2]++;

            if(cur[2] == 4){
                stack.pop();
                while(!stack.isEmpty() && !(pos[0] == stack.peek()[0] && pos[1] == stack.peek()[1])){
                    Return(actions.pop());
                }
            }else{
                cur[2]++;
                stack.push(new int[]{pos[0], pos[1], 0});
            }
        }
    }
}

同问。。。。这个题一直没搞清楚，感觉难点在于不知道房间的大小？然后用set记录位置尽量少走回头路？

我觉得应该用dfs 然后需要开一个stack记录path （或者recursion）

用一个visited标记有没有访问过

最重要的是考虑好cornercase 怎么从现在状态回到上一部状态 什么变了 什么没变 除了坐标还要考虑方向

其实你自己写一个差不多就知道要考虑什么了

就是DFS 唯一的区别就是要手动控制 把move和turn的action封装一下就可以了

然而面试官的意思是不用记录path不用记录visited

lyxuan1208 发表于 2018-3-9 08:03
然而面试官的意思是不用记录path不用记录visited

诶 真的吗
不记录path还可以 就改成recursion就好啦
那部记录visited的话 难道是允许无效率的遍历吗？？

能不能提供下思路呢。。。 虽然知道了也没什么用了估计

greynut 发表于 2018-3-9 08:16
诶 真的吗
不记录path还可以 就改成recursion就好啦
那部记录visited的话 难道是允许无效率的遍历吗？ ...

我同学去面挂了说的，我也不知道思路，不记录visited很容易就成环了，感觉不对。。。
所以假设可以用visited，是假设当前点为原点记录已经访问过的点？

补充内容 (2018-3-9 08:40):
也可能是canMove() 函数自动记录了visited

无论是判断是否存在不重复的路径，还是找最短路径，即使障碍物全部可见，也是NP-complete的
所以肯定是允许重复经过同一个格子的，也不会要求路径最短，自己随便制定一些看上去不太蠢的策略应该就可以了

面博士也考一样的题吗

这题不是17年年初就有