Robot Room Cleaner Solution in Java

Explore More Solutions

C++ Solution |
Python Solution

Problem Description

In the Robot Room Cleaner problem, you are given a robot that can move in four directions (up, down, left, right) and clean the current cell it occupies. The challenge is to design an algorithm that allows the robot to clean all accessible cells in a room represented as a grid, while avoiding obstacles. The robot can only move to open cells and must keep track of the cells it has already cleaned.

Code Solution


/**
 * // This is the robot's control interface.
 * // You should not implement it, or speculate about its implementation
 * interface Robot {
 *   public boolean move();
 *   public void turnLeft();
 *   public void turnRight();
 *   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> seen) {
    seen.add(new Pair<>(i, j));
    robot.clean();

    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);
        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 initial position, cleans the cell, and then attempts to move in all four possible directions. If it can move to a new cell, it recursively calls the DFS function to clean that cell. After exploring all directions, it turns back to its previous position and continues exploring. This ensures that all reachable cells are cleaned without missing any spots.

Time and Space Complexity

Complexity Type Complexity
Time Complexity O(N), where N is the number of cells in the room.
Space Complexity O(N) for the set that keeps track of cleaned cells.

Real-World Example

Imagine a robot vacuum cleaner in your home. It needs to navigate around furniture, avoid stairs, and ensure it cleans every corner of the room. Just like the robot in our problem, it must remember where it has already cleaned to avoid redundancy. If it were to forget, you might end up with a perfectly clean spot in the middle of a dusty room—definitely not the goal!

Similar Problems