489. Robot Room Cleaner

backtracking O(4^{n - m}) time O(n - m) space
n是所有cell的个数 m是障碍的个数
尝试在每个方向上clean一遍

/**
 * // 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<pair<int, int>> dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    unordered_set<string> s;
    int r = 0, c = 0, d = 0;
    void cleanRoom(Robot& robot) {
        auto k = to_string(r) + " " + to_string(c);
        if (s.count(k)) return;
        s.insert(k);
        robot.clean();
        for (int i = 0; i < 4; ++i) { // 每一个cell尝试四个方向
            if (robot.move()) { // 任何一个方向能前进的话
                auto [dr, dc] = dirs[d];
                r += dr;
                c += dc;
                cleanRoom(robot); // 尝试在这个方向上clean（有可能已经clean过，则回退）
                robot.turnRight();
                robot.turnRight();
                robot.move();
                robot.turnRight();
                robot.turnRight();
                r -= dr;
                c -= dc;
            }
            robot.turnRight(); // 尝试下一个方向
            d = (d + 1) % 4;
        }
    }
};