google 扫地机器人

Ostrichi 发表于 2018-3-9 09:10
class robot{
   
    int[] pos;

想问下这个Return(actions.pop());
actions是应该存之前的move的方向么？
然后这行代码的意思是一直往回退直到退到上一格。那是不是只要退一格就好。。不需要while？？？

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

我写了一个方法，楼主看一下是否有问题？
.google  и
public class Solution{
   
    public void turnLeft(int n);
    public void turnRight(int n);
    public boolean move();
    public void clean();
   
    public void cleanRoom()
    {
        Set<int[]> visited = new HashSet<int[]>();
        dfs(0, 0, visited, 0);
    }
   
    private void dfs(int x, int y, Set<int[]> visited, int direction)
    {
        if(visited.contains(pos))
        {
            moveBack(direction);
            return;
        }
        
        int[] pos = {x, y};
        visited.add(pos);
        clean();
        
        // start to clean 4 directions
        turnLeft(0);
        if(move())
        {
            dfs(x, y - 1, visited, 0);
        }
        else
        {
            visited.add(new int[]{x, y - 1});
        }
        
        turnLeft(1);
        if(move())
        {
            dfs(x, y + 1, visited, 1);
        }
        else
        {
            visited.add(new int[]{x, y + 1});
        }
        
        turnLeft(2);
        if(move())
        {
            dfs(x + 1, y, visited, 2);
        }
        else
        {
            visited.add(new int[]{x + 1, y});
        }
        
        turnLeft(3);
        if(move())
        {
            dfs(x, y - 1, visited, 3);
        }
        else
        {
            visited.add(new int[]{x, y - 1});
        }
        
        moveback(directoin);
    }
   
    // move back to previous cell and adjust direction
    private void moveBack(int n)
    {
        turnLeft(2);
        move();
        turnRight(n);
    }
}

补充内容 (2018-4-4 11:45):
moveBack function 有个小bug，应该是下面这样：
turnLeft(2);
        move();
        turnLeft(2);
        turnRight(n);

1. 
   
2. offset = [[0, -1], [1, 0], [0, 1], [-1, 0]]
   
3. 
   
4. def my_clean(robot, visited, x, y):
   
5.     if (x, y) in visited:
   
6.         return
   
7.     robot.clean()
   
8.     visited.add((x, y))
   
9.     for i in range(4):
   
10.         robot.turnLeft()
    
11.         if robot.move():
    
12.             my_clean(robot, visited, x + offset[i][0], y + offset[i][1])
    
13.             
    
14.             # back to original point
    
15.             robot.turnLeft()
    
16.             robot.turnLeft()
    
17.             robot.move()
    
18.         
    
19.             # reset facing direction
    
20.             robot.turnLeft()
    
21.             robot.turnLeft()
    

复制代码

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

請問是這樣嗎？

1. void DFS(Robot myRobot, int x, int y, HashSet<Coordinate> visited){
   
2.         if(visited.contains(new Coordinate(x,y)))
   
3.             return;
   
4.         myRobot.Clean();
   
5.         visited.add(new Coordinate(x, y));
   
6.         int[][] directions = {{-1,0},{0,-1},{1,0},{0,1}};
   
7.         for(int i=0; i<directions.length; i++){
   
8.             TurnLeft(i);
   
9.             if(Move())
   
10.                 DFS(myRobot,x + directions[i][0], y + directions[i][1], visited);
    
11.             else    //if next cell is obstacle or wall, add the next cell to visited
    
12.                 visited.add(new Coordinate(x + directions[i][0], y + directions[i][1]));
    
13.             TurnRight(i);
    
14.         }
    
15.     }
    
16. 
    
17. class Robot{
    
18.     // returns true if next cell is open and robot moves into the cell.
    
19.     // returns false if next cell is obstacle and robot stays on the current cell..
    
20.     boolean Move(){}
    
21. 
    
22.     // Robot will stay on the same cell after calling Turn*. k indicates how
    
23.     // many turns to perform.
    
24.     void TurnLeft(int k){}
    
25.     void TurnRight(int k){}
    
26. 
    
27.     // Clean the current cell.
    
28.     void Clean(){}
    
29. 
    
30.     boolean Move(Direction d){}
    
31. }
    
32. 
    
33. 
    
34. class Coordinate{
    
35.     int x;
    
36.     int y;
    
37.     Coordinate(int x, int y){
    
38.         this.x = x;
    
39.         this.y = y;
    
40.     }
    
41. }

复制代码

lf963 发表于 2018-4-5 05:45
請問是這樣嗎？

you need a moveBack function in the end? I posted one but not sure it's correct. You can take a look.

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

-baidu 1point3acres请问那个Followup 是啥呢？

flyPacific111 发表于 2018-4-4 10:52
我写了一个方法，楼主看一下是否有问题？

public class Solution{

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

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

flyPacific111 发表于 2018-4-4 10:52
我写了一个方法，楼主看一下是否有问题？

public class Solution{

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

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

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

你好，我在试着建模，把这题当 OO 做。
所以想问一下，调用 `move(direction)`，是指机器人会自动转向然后前进一步吗？

补充内容 (2018-4-6 21:46):
`dfs` 的 helper 里面换方向应该是可以直接 `move(direction)` 的对吧？还是必须 `turnxxx()` 再 `move()`?

lf963 发表于 2018-4-5 05:45
請問是這樣嗎？

为什么move成功之后，调用完DFS没有调用方法把机器人放回到调用前的位置？