489. Robot Room Cleaner - Detailed Explanation

Problem Statement

Description:
You are given a robot cleaner in a room modeled as a grid. Each cell in the grid is either empty or blocked. The robot has an interface with the following methods:

• move(): Returns true if the cell in front is open and the robot moves into the cell; returns false if the cell in front is blocked and the robot stays in the current cell.

• turnLeft() / turnRight(): Rotates the robot 90 degrees in the respective direction.

• clean(): Cleans the current cell.

The robot starts at an unknown location facing an unknown direction. The robot has no map of the room, and you cannot access the room grid directly. Your task is to design an algorithm to control the robot to clean the entire room (i.e. every accessible cell). After the robot finishes, all accessible cells should be cleaned.

Example:
Imagine a room represented as a grid (where 1 indicates an open cell and 0 a blocked cell):

Room Grid:
  1  1  1  1
  1  0  1  0
  1  1  1  1

The robot might start at the top-left cell. The goal is to control the robot—using only the provided interface methods—to visit and clean all open cells.

Constraints:

• The room is finite in size.
• The robot can only move to adjacent (up, down, left, right) cells.
• The robot does not know the room dimensions.
• The robot’s initial position and direction are unknown.
• You must not access the grid directly.

Hints

• Hint 1:
  Since you have no global map, you need to explore the room using DFS (depth-first search) or backtracking, starting from the robot’s initial position.

• Hint 2:
  To avoid cleaning the same cell more than once, maintain a set of visited positions. You can treat the robot’s starting position as (0, 0) and compute relative coordinates as you move.

• Hint 3:
  After moving to a new cell, you must backtrack (i.e. return to the previous cell) to explore all paths. Use the robot’s turning methods to reverse direction (e.g. turn 180°) and move back, then restore the original orientation.

Approach: DFS with Backtracking

Key Ideas:

• Marking Visited Cells:
  Represent the robot’s current coordinates (starting at (0, 0)) and record every cell that has been cleaned.

• Exploration with DFS:
  From the current cell, try moving in all 4 directions (up, right, down, left). Use a relative directional mapping (for example, directions = [(-1, 0), (0, 1), (1, 0), (0, -1)] corresponding to up, right, down, left).

• Backtracking:
  After exploring a cell in one direction, the robot must return to the previous cell and restore its orientation. To do this, turn 180° (two turns), move forward (to go back), then turn 180° again.

Detailed Steps:

1. Clean Current Cell:
   Call robot.clean() and mark the cell as visited.

2. Iterate Over 4 Directions:
   For each of the 4 directions, calculate the new coordinates based on the current position and direction. If the new cell hasn’t been visited, try to move into it:

   • If robot.move() returns true, then:

     • Recursively perform DFS from the new cell.

     • Backtrack:
       Turn 180° and call move() to return to the previous cell, then turn 180° again to restore the original direction.

   • Turn right (or left) to change the direction for the next iteration.

3. End Condition:
   The DFS ends when all 4 directions from the current cell have been either visited or blocked.

Python Code