Robot Room Cleaner

给一个robot的api, 问如何清洁一个room.

这题是设计题, 主要还是考虑怎么设计robot的走位, 肯定是dfs没错, 因为room的大小不知道, 所以要按照一定顺序走, 因为robot开始的时候是向上的, 所以按照上右下左开始顺时针走, 并且记录路径. 然后在走不通的时候, 应该统一向一个方向转, 这里选择向右.

/**
 * // 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:
    int dirs[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};// up(default), right, down, left
    unordered_map<int,   unordered_map<int, bool>> v;
    void cleanRoom(Robot& robot) {
        dfs(0,0,0,robot);
    } 
    void dfs(int x, int y, int cur, Robot& robot){
        if(v[x][y]) // if visited
            return;
        robot.clean();
        v[x][y] = 1;
        for(int i = 0; i < 4; i++){
            if(robot.move()){
                int dd = (i + cur) % 4;
                dfs(x + dirs[dd][0], y + dirs[dd][1], dd, robot);
                robot.turnLeft();
                robot.turnLeft(); // 180 degree
                robot.move();
                robot.turnRight();
                robot.turnRight();
            }
            robot.turnRight();
        }
    }
};