489

/**
 * // 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 {
unordered_map<int, bool> vis;
int rowMax = (1<<16);
int d[4][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}};
public:
    void cleanRoom(Robot& robot) {
        dfs(robot, 0, 0, 0);
    }

    void dfs(Robot &robot, int x, int y, int dir){
        int curr = x*rowMax+y;
        if(vis.count(curr)) return;
        vis[curr] = true;
        robot.clean();

        for(int i=0; i<4; i++){
            if(robot.move()){
                dfs(robot, x+d[dir][0], y+d[dir][1], dir);
                robot.turnRight();
                robot.turnRight();
                robot.move();
                robot.turnRight();
                robot.turnRight();
            }
            robot.turnRight();
            dir = (dir+1)%4;
        }
    }

};