Leetcode 489. Robot Room Cleaner

Let's understand what we're being asked to do. We have a robot in an unknown grid with obstacles, and we can only use three APIs: move() (try to move forward), turnLeft() (rotate 90° left), and clean() (clean current cell).

The robot starts at some position facing some direction. We don't have a map, and we don't know the grid boundaries or obstacle locations ahead of time. We can only discover the environment by trying to move.

Key constraint: We must clean every reachable cell exactly once. The robot can't see the whole grid - it can only sense if the cell directly in front is blocked when it tries to move.

Edge cases to consider: What if the robot starts in a corner? What if there are isolated areas we can't reach? How do we avoid cleaning the same cell twice? How do we know when we've explored everything?

Since we can't see the whole grid, we need to explore systematically by trying all four directions from each cell. When we hit a wall or visited cell, we backtrack to try other paths.

The challenge is: without a global map, how do we track which cells we've visited? We need to maintain relative coordinates based on our starting position and current orientation.

By tracking visited coordinates and our current direction, we can avoid revisiting cells even though we're exploring blindly. When we finish exploring all directions from a cell, we can backtrack to the previous cell and continue exploring.

This systematic exploration guarantees we'll visit every reachable cell exactly once, without getting stuck in loops.

Imagine exploring a dark maze with only a flashlight that shows one step ahead. You mark each room you enter with chalk.

From each room, you try all four doors. If a door leads to an unmarked room, you enter it and repeat. If all doors are blocked or lead to marked rooms, you retrace your steps back to the previous room and try other doors.

The key insight: even without seeing the whole maze, this systematic 'try all directions, backtrack when stuck' approach guarantees you'll explore everything reachable.

Use depth-first search with backtracking to explore the grid systematically. Track visited cells using relative coordinates (starting position as origin). From each cell, try all four directions: if a direction leads to an unvisited cell, move there recursively and explore. After exploring all directions, backtrack by moving back and restoring orientation. This ensures every reachable cell is visited exactly once.

def robot_clean(robot):
    """
    Clean all reachable cells using DFS with backtracking.
    Tracks visited cells with relative coordinates (0,0 as start).
    """
    # Direction vectors: up, right, down, left
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    visited = set()
    
    def backtrack(x, y, direction):
        # Mark current cell as visited and clean it
        visited.add((x, y))
        robot.clean()
        
        # Try all 4 directions from current cell
        for i in range(4):
            # Calculate new direction after turning
            new_direction = (direction + i) % 4
            dx, dy = directions[new_direction]
            new_x, new_y = x + dx, y + dy
            
            # If unvisited and robot can move there
            if (new_x, new_y) not in visited and robot.move():
                # Recursively explore from new position
                backtrack(new_x, new_y, new_direction)
                
                # Backtrack: return to previous cell
                # Turn around 180 degrees
                robot.turnRight()
                robot.turnRight()
                robot.move()
                # Turn back to original direction
                robot.turnRight()
                robot.turnRight()
            
            # Turn right to try next direction
            robot.turnRight()
    
    # Start DFS from origin (0, 0) facing up (direction 0)
    backtrack(0, 0, 0)
    
    return visited

• DFS with backtracking in physical space: When exploring unknown environments with limited APIs (no global map access), use DFS with explicit backtracking moves - after exploring a direction, physically return the robot to its previous position and orientation by reversing moves (turn 180°, move forward, turn 180° again) to maintain state consistency.
• Relative coordinate tracking without absolute reference: Track visited cells using a virtual coordinate system starting from (0,0) at the robot's initial position, updating coordinates based on current direction (use direction vectors: up=[0,1], right=[1,0], down=[0,-1], left=[-1,0]) - this allows obstacle detection and cycle prevention without knowing the actual grid layout.
• Direction state management with modular arithmetic: Maintain robot orientation as an integer index (0-3) into a direction array and use modulo operations for turns (right: `(dir + 1) % 4`, left: `(dir + 3) % 4` or `(dir - 1) % 4`) - this elegantly handles circular direction changes without complex conditional logic.
• Visited set for cycle prevention in exploration: Always use a set to track visited coordinates before attempting to move - checking `if neighbor not in visited and robot.move()` prevents infinite loops and redundant cleaning, crucial since the robot can't peek ahead and must attempt moves to discover obstacles.
• Systematic neighbor exploration pattern: Explore all four directions in a fixed clockwise/counterclockwise order (0°, 90°, 180°, 270°) from each cell, turning the robot after each attempt - this systematic approach ensures complete coverage and makes backtracking predictable, preventing missed cells in complex layouts.
• Backtracking in constrained API environments: When working with limited control APIs (can't teleport or query state), implement backtracking by storing the exact sequence of moves needed to return - in this case, the elegant solution is to always return to parent position after exploring each direction, maintaining the robot as a stateful explorer rather than treating it as a passive data structure.