昨天刷到一个很有意思的题目，489. Robot Room Cleaner， 是hard题，我顺便看了下半年内的公司选这道题目面试的tag, google facebook这种大厂非常多次。
这道题做完就会想会不会家里的扫地机器人也是这个算法？你猜你家里的扫地机器人用的是什么算法呢？哈哈肯定不是这个。
这个题目乍一看感觉有点难，因为机器人是randomly安排起始点的，但是题目很清楚地表示了用一个m*n的方格子来作为maze，这个就相当于给了很多限制。然后后面还有机器人到达一个方块的时候，如何知道是面朝什么方向的呢？
这道题的leetcode solution给我们指向了一个maze algorithm的wiki，solution用的就是right-hand rule。这个就让思路很清晰了。另外solution比较tricky的就是仍然用一个矩阵来记录visited node 来帮助backtrack。以起始点为原坐标，构建矩阵。
solution:
class Solution {
int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
Set<Pair<Integer, Integer>> visited = new HashSet<>();
Robot robot;
private void goback() {
robot.turnRight();
robot.turnRight();
robot.move();
robot.turnRight();
robot.turnRight();
}
private void backtrack(int i, int j, int dir) {
visited.add(new Pair(i, j));
robot.clean();
for(int d = 0;d<4;d++) {
int del = (dir + d)%4; // 非常好的去解决方向的问题
int newI = i + directions[del][0];
int newJ = j + directions[del][1];
if(!visited.contains(new Pair(newI, newJ)) && robot.move()) {
backtrack(newI, newJ, del);
goback();
}
robot.turnRight();
}
}
public void cleanRoom(Robot robot) {
this.robot = robot;
backtrack(0,0,0);
}
}
time complexity: O(N−M), where N is a number of cells in the room and M is a number of obstacles.
space complexity: O(N-M)
比较接近的一道题： 130. Surrounded Regions ， 比较轻松的做法就是原地修改值，然后再改回来。
