489. Robot Room Cleaner

https://leetcode.com/problems/robot-room-cleaner/

模拟扫地机器人，初始位置未知，问什么样的指令能让它扫完有障碍物的所有格子。让从一个不事先知道位置的起点开始遍历，和知道位置并没有什么区别，把起点当(0,0)，其它位置存相对坐标。要求模拟真走，因此把backtracking看做退回到同朝向的上个位置，做一下调头回到当前位置再调回来以保证状态和进入前一致。为了保证位置的正确性，DFS不光要记录位置，还要记录朝向，同时dirs数组也要和rotate引起的坐标变化一致。

题目和解法参考了这里。

/**
 * // This is the robot's control interface.
 * // You should not implement it, or speculate about its implementation
 * class Robot {
 *   public:
 *     // Returns true if the cell in front is open and robot moves into the cell.
 *     // Returns false if the cell in front is blocked and robot stays in the current cell.
 *     bool move();
 *
 *     // Robot will stay in the same cell after calling turnLeft/turnRight.
 *     // Each turn will be 90 degrees.
 *     void turnLeft();
 *     void turnRight();
 *
 *     // Clean the current cell.
 *     void clean();
 * };
 */
class Solution {
public:
    vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    void dfs(Robot &robot, int x, int y, int dir, unordered_map<int, unordered_set<int>> &visited) {
        visited[x].insert(y); 
        robot.clean();
        for (int i = 0; i < 4; ++i) {
            int cur = (i + dir) % 4, nx = x + dirs[cur][0], ny = y + dirs[cur][1];
            if (visited.count(nx) && visited[nx].count(ny) || !robot.move()) {
                robot.turnRight();
                continue;
            }
            dfs(robot, nx, ny, cur, visited);
            // 回溯到上个位置，同方向
            // 走回到当前位置
            robot.turnRight();
            robot.turnRight();
            robot.move();
            robot.turnLeft();
            robot.turnLeft();
            // 转到下一个DFS方向
            robot.turnRight();
        }
    }
    void cleanRoom(Robot& robot) {
        unordered_map<int, unordered_set<int>> visited;
        dfs(robot, 0, 0, 0, visited);
    }
};