# 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:

```python
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:

```python
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:

```python
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:

```python
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:

```text
(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:

```python
robot.turnRight()
robot.turnRight()
robot.move()
robot.turnRight()
robot.turnRight()
```

This does four things:

1. Turn around.
2. Move back to the previous cell.
3. Turn around again.
4. Face the original direction.

This is the central trick in the problem.

## Algorithm

Maintain a set:

```python
visited = set()
```

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

Define:

```python
dfs(row, col, direction)
```

where:

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

Inside DFS:

1. Mark `(row, col)` visited.
2. Clean the current cell.
3. Try all four directions.
4. 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.
5. 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

```python
# """
# 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)`:

```python
dfs(0, 0, 0)
```

The third argument `0` means the robot starts facing up.

The directions array encodes clockwise movement:

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

The DFS marks and cleans the current cell:

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

The loop tries four directions:

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

After each attempt, we turn right:

```python
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:

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

Then we recurse:

```python
dfs(next_row, next_col, new_direction)
```

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

```python
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.

```python
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:

```python
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:

```python
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 |