谷歌电面跪经

这个应该用DFS吧，因为更贴切机器人一次只走一条路的行为吧。

reliveinfire 发表于 2017-8-16 14:04
我的想法是dfs traversal, 当从dfs离开, 要回到之前的点, 并且将robot的方向, 找到call dfs时的方向, 不知 ...

请问为什么需要机器人最后回到dfs之前的点

baudelaire 发表于 2017-8-21 20:34
感觉是dfs+backtrack 不过房子太大了可能会爆栈。 写了一下代码 请大神们指教！

请问最后为什么 orient robot to oposite direction of d

8888888 发表于 2017-12-4 08:00
请问最后为什么 orient robot to oposite direction of d

其实就是backtrack到最初的状态 就像一般dfs一样

baudelaire 发表于 2017-8-21 20:34
感觉是dfs+backtrack 不过房子太大了可能会爆栈。 写了一下代码 请大神们指教！

会不会robot一个格子需要先走过去 再走回来的情况
XXOXX
XXOXX
OOSOO
XXOXX

S是出发点 需要先清扫上面 然后返回请扫下面 如果把访问过的点加入memo 是不是不会再访问这一个点呢

谢谢

其实就是搜索，回溯法搜索房间的每一个点，这里要用dfs，因为机器人不能同时出现在两个地方，所以用不了bfs。

这非常像一道AI中的search题目。

根据AI的思想， 首先根据提供的API定义出自己想要的actions（三个方向移动和返回原来的位置），然后利用这些action解决问题。

1.     interface Robot {
   
2.         Stack<String> actions = new Stack<>(); // store completed actions
   
3.         Stack<String> plans = new Stack<>();    // store future actions
   
4.         int[] curPosition = new int[2]; // mark the position in the robot's view
   
5.         Set<String> visited = new HashSet<>(); // store the visited position
   
6.         // actions
   
7. 
   
8.         // returns true if next cell is open and robot moves into the cell.
   
9.         // returns false if next cell is obstacle and robot stays on the current cell.
   
10.         boolean Move();
    
11.         // Robot will stay on the same cell after calling Turn*. k indicates hown many turns to perform.
    
12.         void TurnLeft(int k);
    
13.         void TurnRight(int k);
    
14.         // Clean the current cell.
    
15.         void Clean();
    
16.         boolean Move(Direction d);
    
17. 
    
18.         // keep the facing direction when moving left / right
    
19.         // String[] actions = new String[]{"Forward", "Left", "Right"};
    
20. 
    
21.         boolean MoveForward(){
    
22.             // actions.push("Forward");
    
23. 
    
24.             boolean success = Move();
    
25.             if(success) ++curPosition[1];
    
26.         }
    
27. 
    
28.         boolean MoveLeft(){
    
29.             // actions.push("Left");
    
30.             
    
31.             TurnLeft(1);
    
32.             boolean success = Move();
    
33.             if(success) --curPosition[0];
    
34.             TurnRight(1);
    
35.             return success;
    
36.         }
    
37. 
    
38.         boolean MoveRight(){
    
39.             // actions.push("Right");
    
40.             TurnRight(1);
    
41.             boolean success = Move();
    
42.             if(success) ++curPosition[0];
    
43.             TurnLeft(1);
    
44.             return success;
    
45.         }
    
46. 
    
47. 
    
48.         // explore new space
    
49.         boolean Actuator(String direction){
    
50.             if(direction.equals("Forward")){
    
51.                 actions.push(direction);
    
52.                 return MoveForward();
    
53.             }
    
54.             if(direction.equals("Left")) {
    
55.                 actions.push(direction);
    
56.                 return MoveLeft();
    
57.             }
    
58.             if(direction.equals("Right")){
    
59.                 actions.push(direction);   
    
60.                 return MoveRight();
    
61.             }
    
62.             return false;
    
63.         }
    
64. 
    
65.         // return to the previous position
    
66.         boolean Return(){
    
67.             String lastAction = stack.pop();
    
68.             if(lastAction.equals("Left")) return MoveRight();
    
69.             if(lastAction.equals("Right")) return MoveLeft();
    
70.             if(lastAction.equals("Forward")) return MoveBackforward();
    
71.         }
    
72. 
    
73. 
    
74.         // main function
    
75.         boolean Solver(Robot robot){
    
76.             
    
77.             String posStr = posStr = curPosition[0] + "," + curPosition[1];
    
78.             visited.add(posStr);
    
79.             Clean();
    
80.             plans.push("Forward");
    
81.             plans.push("Left");
    
82.             plans.push("Right");
    
83.             while(!plans.empty()){
    
84.                 String plan = plans.pop();
    
85.                 if(!Actuator(plan)) {
    
86.                     actions.pop();
    
87.                     continue;
    
88.                 }
    
89.                 posStr = curPosition[0] + "," + curPosition[1];
    
90.                 if(!visited.contains(posStr)){
    
91.                     Clean();
    
92.                     visited.add(posStr);
    
93.                     plans.push("Forward");
    
94.                     plans.push("Left");
    
95.                     plans.push("Right");
    
96.                 }else{
    
97.                     Return();
    
98.                 }
    
99.             }
    
100.             return true;
     
101.         }
     
102. 
     
103.     }

复制代码

baudelaire 发表于 2017-8-21 20:34
感觉是dfs+backtrack 不过房子太大了可能会爆栈。 写了一下代码 请大神们指教！

对这段代码不理解，
                if(this.Move()){
                    dfsClean(nx, ny, nd, memo);// take care to orient to oposite direction of nd
                    // move back and turn to nd
                    this.Move();
                    // reset to direction before
                    this.TurnRight(2);
                }else{
是不是应该：
                if(this.Move()){
                    dfsClean(nx, ny, nd, memo);// take care to orient to oposite direction of nd
                    // move back and turn to nd
                    this.TurnRight(2);
                    this.Move();
                    // reset to direction before
                    this.TurnRight(2);
                }else{

baudelaire 发表于 2017-8-21 20:34
感觉是dfs+backtrack 不过房子太大了可能会爆栈。 写了一下代码 请大神们指教！

谢谢lz的代码！我感觉LZ第17行这里应该也需要把ncode加入memo？否则机器人会回头吧？

一个考完托福的废人 发表于 2018-1-1 04:12
这非常像一道AI中的search题目。

根据AI的思想， 首先根据提供的API定义出自己想要的actions（三个方向 ...

感谢层主但我有个问题啊，我们不知道机器人最开始的朝向，比如是面向上方还是面向下方，这个时候你记录的curpos[2]的这个数组就完全反了啊