刷题（14）489. Robot Room Cleaner

昨天刷到一个很有意思的题目，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 ， 比较轻松的做法就是原地修改值，然后再改回来。