Skip to content

489. Robot Room Cleaner 👍

  • Time: $O(mn - |\text{obstacles}|)$
  • Space: $O(mn - |\text{obstacles}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * // 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 std::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:
  void cleanRoom(Robot& robot) {
    dfs(robot, 0, 0, 0, unordered_set<pair<int, int>, PairHash>());
  }

 private:
  static constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

  struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
      return p.first ^ p.second;
    }
  };

  void dfs(Robot& robot, int i, int j, int d,
           unordered_set<pair<int, int>, PairHash>&& seen) {
    seen.insert({i, j});
    robot.clean();

    // Explore clockwise: 0: ^, 1: >, 2: v, 3: <
    // The order is important since the idea is always turning right.
    for (int k = 0; k < 4; ++k) {
      const int newD = (d + k) % 4;
      const int x = i + dirs[newD][0];
      const int y = j + dirs[newD][1];
      if (!seen.contains({x, y}) && robot.move()) {
        dfs(robot, x, y, newD, std::move(seen));
        // Go back to the previous cell.
        robot.turnRight();
        robot.turnRight();
        robot.move();
        // Go back to the original direction.
        robot.turnRight();
        robot.turnRight();
      }
      robot.turnRight();  // Always turn the robot clockwise.
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * // This is the robot's control interface.
 * // You should not implement it, or speculate about its implementation
 * interface Robot {
 *   // 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.
 *   public boolean move();
 *
 *   // Robot will stay in the same cell after calling turnLeft/turnRight.
 *   // Each turn will be 90 degrees.
 *   public void turnLeft();
 *   public void turnRight();
 *
 *   // Clean the current cell.
 *   public void clean();
 * }
 */

class Solution {
  public void cleanRoom(Robot robot) {
    dfs(robot, 0, 0, 0, new HashSet<>());
  }

  private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

  private void dfs(Robot robot, int d, int i, int j, Set<Pair<Integer, Integer>> seen) {
    seen.add(new Pair<>(i, j));
    robot.clean();

    // Explore clockwise: 0: ^, 1: >, 2: v, 3: <
    // The order is important since the idea is always turning right.
    for (int k = 0; k < 4; ++k) {
      final int newD = (d + k) % 4;
      final int x = i + dirs[newD][0];
      final int y = j + dirs[newD][1];
      if (!seen.contains(new Pair<>(x, y)) && robot.move()) {
        dfs(robot, newD, x, y, seen);
        // Go back to the previous cell.
        robot.turnRight();
        robot.turnRight();
        robot.move();
        // Go back to the original direction.
        robot.turnRight();
        robot.turnRight();
      }
      robot.turnRight(); // Always turn the robot clockwise.
    }
  }
}