Robot Room Cleaner Solution in C++

Problem Description

Imagine you have a robot that’s been given the monumental task of cleaning your room. Yes, that’s right! A robot is doing what you’ve been avoiding for weeks. The catch? It can only move in a grid-like fashion and can’t see beyond its immediate surroundings. So, if it encounters a wall, it’s as clueless as a cat in a dog park.

The problem is simple: you need to help this poor robot navigate through the room, clean every cell, and avoid obstacles. Think of it as a game of chess, but instead of knights and bishops, you have a robot that’s just trying to make your life easier (and probably plotting to take over the world while it’s at it).

Code Solution


/**
 * // 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, PairHash>());
  }

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

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

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

    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));
        robot.turnRight();
        robot.turnRight();
        robot.move();
        robot.turnRight();
        robot.turnRight();
      }
      robot.turnRight();
    }
  }
};

Approach Explanation

The solution employs a depth-first search (DFS) strategy to explore the room. The robot starts at the origin (0, 0) and cleans the current cell. It then attempts to move in all four possible directions (up, right, down, left) in a clockwise manner. If it encounters a cell that it hasn’t cleaned yet and can move into, it recursively cleans that cell. After exploring all directions, it backtracks to the previous cell, ensuring that it can navigate the room efficiently.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N), where N is the number of cells in the room. The robot will clean each cell once.
Space Complexity	O(N) for the set that keeps track of cleaned cells.

Real-World Example

Picture this: you’re hosting a party, and your robot is your unsung hero, cleaning up after your guests. It’s like having a personal maid who doesn’t complain about the mess. The robot navigates through the chaos, ensuring every corner is spotless, while you sip on your drink, blissfully unaware of the crumbs under the couch.