LeetCode 489: Robot Room Cleaner

Problem Restatement

We control a robot cleaner inside a room modeled as a grid.

Each cell is either:

Value	Meaning
`1`	Open cell
`0`	Blocked cell

But the algorithm does not receive the grid directly.

Instead, we only control the robot through four APIs:

robot.move()
robot.turnLeft()
robot.turnRight()
robot.clean()

The robot starts at an unknown open cell and initially faces up. The room boundary is surrounded by walls. All open cells are connected. We need to clean every reachable open cell using only the robot APIs. The input grid is only used internally by the judge, so the solution must work without seeing the room layout.

Input and Output

Item	Meaning
Input	A `Robot` object controlled by APIs
Output	Nothing returned
Goal	Clean all reachable open cells
Constraint	The room layout is hidden
Starting direction	Facing up

The interface is conceptually:

class Robot:
    def move(self) -> bool:
        ...

    def turnLeft(self) -> None:
        ...

    def turnRight(self) -> None:
        ...

    def clean(self) -> None:
        ...

move() returns True if the cell in front is open and the robot moves into it. It returns False if the cell is blocked, and the robot stays in the current cell.

turnLeft() and turnRight() rotate the robot by 90 degrees without changing its cell.

clean() cleans the current cell.

Examples

Example 1 uses a hidden room like:

room = [
    [1, 1, 1, 1, 1, 0, 1, 1],
    [1, 1, 1, 1, 1, 0, 1, 1],
    [1, 0, 1, 1, 1, 1, 1, 1],
    [0, 0, 0, 1, 0, 0, 0, 0],
    [1, 1, 1, 1, 1, 1, 1, 1],
]
row = 1
col = 3

The robot starts at room[1][3].

The algorithm does not know this grid or this coordinate. It only knows whether move() succeeds or fails.

The expected result is not a returned list. The judge checks that the robot cleaned every reachable open cell.

First Thought: Treat It Like Grid DFS

If the grid were visible, we could do normal DFS:

dfs(row, col):
    mark visited
    clean cell
    for each neighbor:
        if open and not visited:
            dfs(neighbor)

But here we do not know:

Unknown	Why it matters
Absolute position	The robot does not tell us its row and column
Walls	We discover them only when `move()` fails
Neighbor status	We must physically try moving
Orientation	Movement depends on the direction the robot faces

So we need a DFS that works by controlling the robot physically.

Key Insight

We can create our own coordinate system.

Treat the starting cell as:

(0, 0)

Since the robot starts facing up, define directions like this:

Direction index	Meaning	Delta
`0`	Up	`(-1, 0)`
`1`	Right	`(0, 1)`
`2`	Down	`(1, 0)`
`3`	Left	`(0, -1)`

When the robot successfully moves forward, we update the relative coordinate according to the direction.

We do not need absolute room coordinates. We only need a consistent map of where we have already been relative to the start.

Physical Backtracking

Normal DFS returns from recursion automatically.

But here, after the robot moves into a neighbor and finishes exploring it, the robot is physically still at that neighbor.

Before exploring the next direction from the parent cell, we must move the robot back to the parent cell and restore its orientation.

The backtracking maneuver is:

robot.turnRight()
robot.turnRight()
robot.move()
robot.turnRight()
robot.turnRight()

This does four things:

Turn around.
Move back to the previous cell.
Turn around again.
Face the original direction.

This is the central trick in the problem.

Algorithm

Maintain a set:

visited = set()

Each item is a relative coordinate (row, col).

Define:

dfs(row, col, direction)

where:

Parameter	Meaning
`row, col`	Robot’s relative coordinate
`direction`	Direction the robot currently faces

Inside DFS:

Mark (row, col) visited.
Clean the current cell.
Try all four directions.
For each direction:
- Compute the next relative coordinate.
- If it has not been visited, call robot.move().
- If move() succeeds, DFS into that cell.
- After returning, physically backtrack.
Turn right after each attempt so the robot checks the next direction.

Correctness

The algorithm marks each discovered open cell as visited and cleans it immediately.

From every visited cell, it attempts all four directions. If moving forward succeeds, the target cell is open. If that relative coordinate has not been visited, the algorithm recursively explores it.

The backtracking maneuver returns the robot to the exact previous cell and restores the previous orientation. Therefore, after exploring one neighbor, the robot is in the correct state to try the next neighbor.

Because all open cells are connected, every reachable open cell can be reached by some path from the start. DFS follows every successful movement path unless the target coordinate was already visited. Therefore, every reachable open cell is eventually visited and cleaned.

The visited set prevents infinite loops and repeated cleaning of the same relative coordinate.

Thus the algorithm cleans the entire reachable room.

Complexity

Metric	Value	Why
Time	`O(R - C)` conceptually `O(R)`	Each reachable cell is visited once, and each cell tries four directions
Space	`O(R)`	The visited set and recursion stack store reachable cells

Here, R is the number of reachable open cells.

The robot may perform a constant number of turns and moves per direction attempt, so the total API calls are linear in the number of reachable cells.

Implementation

# """
# This is the robot's control interface.
# You should not implement it, or speculate about its implementation.
#
# class Robot:
#     def move(self):
#         """
#         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.
#         """
#
#     def turnLeft(self):
#         """
#         Robot stays in the same cell after calling turnLeft.
#         Each turn is 90 degrees.
#         """
#
#     def turnRight(self):
#         """
#         Robot stays in the same cell after calling turnRight.
#         Each turn is 90 degrees.
#         """
#
#     def clean(self):
#         """
#         Clean the current cell.
#         """
# """

class Solution:
    def cleanRoom(self, robot):
        visited = set()

        directions = [
            (-1, 0),  # up
            (0, 1),   # right
            (1, 0),   # down
            (0, -1),  # left
        ]

        def go_back():
            robot.turnRight()
            robot.turnRight()
            robot.move()
            robot.turnRight()
            robot.turnRight()

        def dfs(row, col, direction):
            visited.add((row, col))
            robot.clean()

            for offset in range(4):
                new_direction = (direction + offset) % 4
                dr, dc = directions[new_direction]
                next_row = row + dr
                next_col = col + dc

                if (next_row, next_col) not in visited and robot.move():
                    dfs(next_row, next_col, new_direction)
                    go_back()

                robot.turnRight()

        dfs(0, 0, 0)

Code Explanation

The starting cell is treated as (0, 0):

dfs(0, 0, 0)

The third argument 0 means the robot starts facing up.

The directions array encodes clockwise movement:

directions = [
    (-1, 0),
    (0, 1),
    (1, 0),
    (0, -1),
]

The DFS marks and cleans the current cell:

visited.add((row, col))
robot.clean()

The loop tries four directions:

for offset in range(4):
    new_direction = (direction + offset) % 4

After each attempt, we turn right:

robot.turnRight()

This keeps the physical robot direction synchronized with the loop.

If the next cell has not been visited and move() succeeds, the robot has physically moved there:

if (next_row, next_col) not in visited and robot.move():

Then we recurse:

dfs(next_row, next_col, new_direction)

After the recursive call, we must physically return to the previous cell:

go_back()

The go_back helper preserves the orientation after returning.

Testing

This problem cannot be tested with a normal direct function return because LeetCode supplies a hidden Robot implementation.

For local testing, we can build a mock robot.

class MockRobot:
    def __init__(self, room, row, col):
        self.room = room
        self.row = row
        self.col = col
        self.direction = 0
        self.cleaned = set()

        self.directions = [
            (-1, 0),
            (0, 1),
            (1, 0),
            (0, -1),
        ]

    def move(self):
        dr, dc = self.directions[self.direction]
        nr = self.row + dr
        nc = self.col + dc

        if (
            nr < 0
            or nr >= len(self.room)
            or nc < 0
            or nc >= len(self.room[0])
            or self.room[nr][nc] == 0
        ):
            return False

        self.row = nr
        self.col = nc
        return True

    def turnLeft(self):
        self.direction = (self.direction - 1) % 4

    def turnRight(self):
        self.direction = (self.direction + 1) % 4

    def clean(self):
        self.cleaned.add((self.row, self.col))

Test helper:

def reachable_cells(room, start_row, start_col):
    stack = [(start_row, start_col)]
    seen = {(start_row, start_col)}

    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    while stack:
        row, col = stack.pop()

        for dr, dc in directions:
            nr = row + dr
            nc = col + dc

            if (
                0 <= nr < len(room)
                and 0 <= nc < len(room[0])
                and room[nr][nc] == 1
                and (nr, nc) not in seen
            ):
                seen.add((nr, nc))
                stack.append((nr, nc))

    return seen

Tests:

def run_tests():
    room = [
        [1, 1, 1, 1, 1, 0, 1, 1],
        [1, 1, 1, 1, 1, 0, 1, 1],
        [1, 0, 1, 1, 1, 1, 1, 1],
        [0, 0, 0, 1, 0, 0, 0, 0],
        [1, 1, 1, 1, 1, 1, 1, 1],
    ]

    robot = MockRobot(room, 1, 3)
    Solution().cleanRoom(robot)

    assert robot.cleaned == reachable_cells(room, 1, 3)

    single = [[1]]
    robot = MockRobot(single, 0, 0)
    Solution().cleanRoom(robot)

    assert robot.cleaned == {(0, 0)}

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
Large hidden room	Checks full DFS and backtracking
Single open cell	Checks smallest reachable area
Mock robot	Verifies the solution uses only the allowed API