谷歌电面跪经

这个题是机器人扫描，不能BFS吧，就是DFS+backtracing

测了下貌似没问题。。。后面那四个helper应该还可以优化一下，懒得优化了。。。欢迎指正
假设机器人开始向上：

1. #include <iostream>
   
2. #include <vector>
   
3. #include <unordered_map>
   
4. #include <unordered_set>
   
5. using namespace std;
   
6. 
   
7. class Robot {
   
8. public:
   
9.   Robot(vector<string>& grid, int i, int j) : grid(grid), i(i), j(j) {
   
10.    
    
11.   }
    
12.   bool Move() {
    
13.     if (i + di < 0 || i + di >= grid.size() || j + dj < 0 || j + dj >= grid[i].size() || grid[i + di][j + dj] == '+')
    
14.       return false;
    
15.     i += di;
    
16.     j += dj;
    
17.     return true;
    
18.   }
    
19. 
    
20.   // Robot will stay on the same cell after calling Turn*. k indicates how
    
21.   // many turns to perform.
    
22.   int ddi[4] = {0, 1, 0, -1};
    
23.   int ddj[4] = {1, 0, -1, 0};
    
24.   void TurnRight(int k) {
    
25.     int ii = 0;
    
26.     for (; ii < 4; ++ii) {
    
27.       if (ddi[ii] == di && ddj[ii] == dj)
    
28.         break;
    
29.     }
    
30.     int iii = (ii + k) % 4;
    
31.     di = ddi[iii];
    
32.     dj = ddj[iii];
    
33.   }
    
34.   void TurnLeft(int k) {
    
35.     int ii = 0;
    
36.     for(; ii < 4; ++ii) {
    
37.       if (ddi[ii] == di && ddj[ii] == dj)
    
38.         break;
    
39.     }
    
40.     int iii = (ii - k) % 4;
    
41.     di = ddi[iii];
    
42.     dj = ddj[iii];
    
43.   }
    
44.   // Clean the current cell.
    
45.   void Clean() {
    
46.     grid[i][j] = ' ';
    
47.   }
    
48. private:
    
49.   vector<string>& grid;
    
50.   int i;
    
51.   int j;
    
52.   int di = 1;
    
53.   int dj = 0;
    
54. };
    
55. // after each move, recover the direction of robots
    
56. bool moveLeft(Robot& r) {
    
57.   r.TurnRight(3);
    
58.   bool possible = r.Move();
    
59.   r.TurnRight(1);
    
60.   return possible;
    
61. }
    
62. 
    
63. bool moveRight(Robot& r) {
    
64.   r.TurnRight(1);
    
65.   bool possible = r.Move();
    
66.   r.TurnRight(3);
    
67.   return possible;
    
68. }
    
69. 
    
70. bool moveUp(Robot& r) {
    
71.   bool possible = r.Move();
    
72.   return possible;
    
73. }
    
74. 
    
75. bool moveDown(Robot& r) {
    
76.   r.TurnRight(2);
    
77.   bool possible = r.Move();
    
78.   r.TurnRight(2);
    
79.   return possible;
    
80. }
    
81. 
    
82. void helper1(Robot& r, unordered_map<int, unordered_set<int> >& visited, int i, int j) {
    
83.   // left, up, down
    
84.   if (visited.count(i) && visited[i].count(j))
    
85.     return;
    
86.   r.Clean();
    
87.   //r.print();
    
88.   visited[i].insert(j);
    
89.   if (moveLeft(r)) {
    
90.     helper1(r, visited, i, j - 1);
    
91.     moveRight(r);
    
92.   }
    
93.   if (moveUp(r)) {
    
94.     helper1(r, visited, i + 1, j);
    
95.     moveDown(r);
    
96.   }
    
97.   if (moveDown(r)) {
    
98.     helper1(r, visited, i - 1, j);
    
99.     moveUp(r);
    
100.   }
     
101.   return;
     
102. }
     
103. 
     
104. void helper2(Robot& r, unordered_map<int, unordered_set<int> >& visited, int i, int j) {
     
105.   // up left right
     
106.   if (visited.count(i) && visited[i].count(j))
     
107.     return;
     
108.   r.Clean();
     
109.   visited[i].insert(j);
     
110.   if (moveUp(r)) {
     
111.     helper2(r, visited, i + 1, j);
     
112.     moveDown(r);
     
113.   }
     
114.   if (moveLeft(r)) {
     
115.     helper2(r, visited, i, j - 1);
     
116.     moveRight(r);
     
117.   }
     
118.   if (moveRight(r)) {
     
119.     helper2(r, visited, i, j + 1);
     
120.     moveLeft(r);
     
121.   }
     
122.   return;
     
123. }
     
124. 
     
125. void helper3(Robot& r, unordered_map<int, unordered_set<int> >& visited, int i, int j) {
     
126.   // up right down
     
127.   if (visited.count(i) && visited[i].count(j))
     
128.     return;
     
129.   r.Clean();
     
130.   visited[i].insert(j);
     
131.   if (moveUp(r)) {
     
132.     helper3(r, visited, i + 1, j);
     
133.     moveDown(r);
     
134.   }
     
135.   if (moveRight(r)) {
     
136.     helper3(r, visited, i, j + 1);
     
137.     moveLeft(r);
     
138.   }
     
139.   if (moveDown(r)) {
     
140.     helper3(r, visited, i - 1, j);
     
141.     moveUp(r);
     
142.   }
     
143.   return;
     
144. }
     
145. 
     
146. void helper4(Robot& r, unordered_map<int, unordered_set<int> >& visited, int i, int j) {
     
147.   // left down right                                                                                                                        
     
148.   if (visited.count(i) && visited[i].count(j))
     
149.     return;
     
150.   r.Clean();
     
151.   visited[i].insert(j);
     
152.   if (moveLeft(r)) {
     
153.     helper4(r, visited, i, j - 1);
     
154.     moveRight(r);
     
155.   }
     
156.   if (moveDown(r)) {
     
157.     helper4(r, visited, i - 1, j);
     
158.     moveUp(r);
     
159.   }
     
160.   if (moveRight(r)) {
     
161.     helper4(r, visited, i, j + 1);
     
162.     moveLeft(r);
     
163.   }
     
164.   return;
     
165. }
     
166. 
     
167. void cleanAll(Robot& r) {
     
168.   unordered_map<int, unordered_set<int> > visited;
     
169.   helper1(r, visited, 0, 0);
     
170.   visited.clear();
     
171.   helper2(r, visited, 0, 0);
     
172.   visited.clear();
     
173.   helper3(r, visited, 0, 0);
     
174.   visited.clear();
     
175.   helper4(r, visited, 0, 0);
     
176. }
     
177. 
     
178. int main() {
     
179.   vector<string> layout({
     
180.       "++++++++++",
     
181.         "+........+",
     
182.         "+........+",
     
183.         "+.+......+",
     
184.         "++++.+++++",
     
185.         "+.....+",
     
186.         "+++++++"
     
187.         });
     
188.   Robot r(layout, 2, 4);
     
189.   cleanAll(r);
     
190.   for (auto s: layout)
     
191.     cout << s << endl;
     
192.   return 0;
     
193. }
     

复制代码

endofunctor 发表于 2017-8-19 19:50
测了下貌似没问题。。。后面那四个helper应该还可以优化一下，懒得优化了。。。欢迎指正
假设机器人开始向 ...

层主辛苦了，，，但是当时面试时的题目是，要用他给的inteface Robot里面的methods，并不需要自己实现这些methods。。。

不zhiwei何 发表于 2017-8-21 11:58
层主辛苦了，，，但是当时面试时的题目是，要用他给的inteface Robot里面的methods，并不需要自己实现这 ...

多谢多谢。。。因为没啥办法模拟所以只好自己写一个了。。。82行开始才是干货

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

我觉得基本就是这个解法，主要就是注意是机器人，保证方向在进入深层递归中不变，同时从深层递归返回时调整方向

感觉是dfs+backtrack 不过房子太大了可能会爆栈。 写了一下代码 请大神们指教！

1.    
   
2.     int[][] dirs = new int[][]{{0,1}, {1,0}, {0,-1}, {-1,0}};
   
3.     Set<String> memo = new HashSet<>();
   
4.     public void dfsClean(int x, int y, int d, Set<String> memo){
   
5.         // x,y: position, d: direction
   
6.         String hcode = x+":"+y;
   
7.         this.Clean();
   
8.         memo.add(hcode);
   
9.         for(int i=0; i<4; i++){
   
10.             this.TurnRight(i>0?1:0); // first go ahead, then each time one turn
    
11.             int nd = (d+i)%4;
    
12.             int nx = x+dirs[nd][0];
    
13.             int ny = y+dirs[nd][1];
    
14.             String ncode = nx+":"+ny;
    
15.             if(!memo.contains(ncode)){
    
16.                 if(this.Move()){
    
17.                     dfsClean(nx, ny, nd, memo);// take care to orient to oposite direction of nd
    
18.                     // move back and turn to nd
    
19.                     this.Move();
    
20.                     // reset to direction before
    
21.                     this.TurnRight(2);
    
22.                 }else{
    
23.                     // obstacle found, remember it
    
24.                     memo.add(ncode);
    
25.                 }
    
26.             }
    
27.         }
    
28.         // orient robot to oposite direction of d
    
29.         this.TurnRight(2);
    
30.     }
    

复制代码

补充内容 (2017-8-21 20:37):
最后两行应该为
        // orient robot to oposite direction of d
        this.TurnRight(3);

补充内容 (2017-8-21 20:39):
感觉这题不应该使用input里边那些字符，因为扫地机器人是盲扫，根本不知道房子的地图，面试官给个input估计是为了便于理解

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

感觉只用一个hash set存相对坐标就行了， 机器人不管起始放在哪都设成(0,0)。 另外大神你这个代码会让机器人随后停止的位置和起始位置不一样，因为你最后backtrack的时候把机器人往下移了一格

看上去有点类似口袋宝石的一道面经 机器人格子
http://www.1point3acres.com/bbs/thread-287234-1-1.html

1. #include <iostream>
   
2. #include <vector>
   
3. #include <stack>
   
4. #include <unordered_set>
   
5. #include <unordered_map>
   
6. using namespace std;
   
7. 
   
8. // r, c are coordinates, turn : track how many turns made in the current position
   
9. struct int3{
   
10.     int r, c, turn;
    
11. };
    
12. 
    
13. class Robot {
    
14. public:
    
15.     // returns true if next cell is open and robot moves into the cell.
    
16.     // returns false if next cell is obstacle and robot stays on the current cell.
    
17.     int m, n, r, c;
    
18.     vector<vector<char>> maze;
    
19.     stack<int3> sk;
    
20.     unordered_set<int> visited;
    
21.     int dr[4] = {-1,1,0,0}, dc[4] = {0,0,-1,1};
    
22.     int robotDir;
    
23.    
    
24.     // assume robot facing upward initially
    
25.     Robot(vector<vector<char>>& maze, int r, int c) {
    
26.         this->maze = maze;
    
27.         this->r = r;
    
28.         this->c = c;
    
29.         m = maze.size(), n = maze[0].size();
    
30.         sk.push({r, c, 0}); // to guard against stack overflow, I write the function call stack explicitly by myself  instead of doing recursion.
    
31.         visited.insert(r*n + c);
    
32.         robotDir = 0; // track robot last facing direction before hit this grid point
    
33.         // robotDir : 0 up, 1 right, 2 down, 3 left
    
34.     }
    
35.    
    
36.     bool Move(){
    
37.         r = sk.top().r, c = sk.top().c;
    
38.         int& countTurn = sk.top().turn;
    
39.         
    
40.         if(countTurn == 0) {
    
41.             Clean(); // in a new position, clean it
    
42.             robotDir--; // make robot start search the current facing direction first
    
43.         }
    
44.         
    
45.         if(countTurn < 4) { // search neighbors
    
46.             TurnRight(1); // adjust robot facing position
    
47.             countTurn++;
    
48.             
    
49.             int rr = r + dr[robotDir], cc = c + dc[robotDir];
    
50.             if(rr >= 0 && rr < m && cc >= 0 && cc < n && maze[rr][cc] != '+' && !visited.count(rr*n + cc)) {
    
51.                 visited.insert(rr*n + cc);
    
52.                 sk.push({rr, cc, 0});
    
53.                 return true; // explore a new neighbor
    
54.             }
    
55.             else return false; // obstacle, stay there
    
56.         }
    
57.         else { // if all neighbors have been searched, go back
    
58.             // reset to initial direction before entering this position
    
59.             TurnRight(1); // adjust robot facing position
    
60.             
    
61.             // go back()
    
62.             sk.pop();
    
63.             return false;
    
64.         }
    
65.     }
    
66.    
    
67.     // Robot will stay on the same cell after calling Turn*. k indicates how
    
68.     // many turns to perform.
    
69.     void TurnLeft(int k) {}
    
70.     void TurnRight(int k) {robotDir = (robotDir + 1) % 4;}
    
71.    
    
72.     // Clean the current cell.
    
73.     void Clean() {
    
74.         maze[r][c] = 'O';
    
75.     }
    
76.    
    
77.     void printBoard() {
    
78.         cout << endl;
    
79.         for(auto row : maze) {
    
80.             for(char c : row) {
    
81.                 cout << c;
    
82.             }
    
83.             cout << endl;
    
84.         }
    
85.     }
    
86. };
    
87. 
    
88. 
    
89. int main(int argc, const char * argv[]) {
    
90.     // insert code here...
    
91.     vector<string> input = {
    
92.         "++++++++++",
    
93.         "+........+",
    
94.         "+...^....+",
    
95.         "+.+......+",
    
96.         "++++.+++++",
    
97.         "+.....+",
    
98.         "+++++++"
    
99.     };
    
100.     vector<vector<char>> maze;
     
101.     for(string s : input){
     
102.         maze.push_back(vector<char>({}));
     
103.         for(char c : s) {
     
104.             maze.back().push_back(c);
     
105.         }
     
106.     }
     
107.     Robot rob(maze, 2, 2);
     
108.     while(!rob.sk.empty()) {
     
109.         rob.Move();
     
110.         rob.printBoard();
     
111.     }
     
112.     return 0;
     
113. }

复制代码

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