> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Robot Room Cleaner Python Solution with Tests

> Tested Python solution for LeetCode 489 with 14 pytest cases. Generate a practice environment with lcpy.

LeetCode 489, [Hard](/catalog/hard). Topics: [Backtracking](/catalog/topics/backtracking), [Interactive](/catalog/topics/interactive). [View on LeetCode](https://leetcode.com/problems/robot-room-cleaner/description/).

Generate this problem as a practice environment: tested reference solution, 14 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 489   # by problem number
lcpy gen -s robot_room_cleaner   # by problem name
```

## Problem

You are controlling a robot that is located somewhere in a room. The room is modeled as an `m x n` binary grid where `0` represents a wall and `1` represents an empty slot.

The robot starts at an unknown location in the room that is guaranteed to be empty, and you do not have access to the grid, but you can move the robot using the given API `Robot`.

You are tasked to use the robot to clean the entire room (i.e. clean every empty cell in the room). The robot with the four given APIs can move forward, turn left, or turn right. Each turn is `90` degrees.

When the robot tries to move into a wall cell, its bumper sensor detects the obstacle, and it stays on the current cell.

Design an algorithm to clean the entire room using the following APIs:

```
interface Robot {
  // returns true if next cell is open and robot moves into the cell.
  // returns false if next cell is obstacle and robot stays on the current cell.
  boolean move();

  // Robot will stay on the same cell after calling turnLeft/turnRight.
  // Each turn will be 90 degrees.
  void turnLeft();
  void turn_right();

  // Clean the current cell.
  void clean();
}
```

**Note** that the initial direction of the robot will be facing up. You can assume all four edges of the grid are all surrounded by a wall.

### Examples

![Example 1](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/0400-0499/0489.Robot%20Room%20Cleaner/images/lc-grid.jpg)

```
Input: 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
Output: Robot cleaned all rooms.
Explanation: All grids in the room are marked by either 0 or 1. 0 means the cell is blocked, while 1 means the cell is accessible. The robot initially starts at the position of row=1, col=3.
```

```
Input: room = [[1]], row = 0, col = 0
Output: Robot cleaned all rooms.
```

### Constraints

* `m == room.length`
* `n == room[i].length`
* `1 <= m <= 100`
* `1 <= n <= 200`
* `room[i][j]` is either `0` or `1`.
* `0 <= row < m`
* `0 <= col < n`
* `room[row][col] == 1`
* All the empty cells can be visited from the starting position.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/robot_room_cleaner/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/robot_room_cleaner/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Robot:
    # Test-harness API: backs the interactive move/turn/clean interface with the grid
    def __init__(self, room: list[list[int]], row: int, col: int) -> None:
        self.room = room
        self.row = row
        self.col = col
        self.direction = 0  # 0 up, 1 right, 2 down, 3 left
        self.cleaned: set[tuple[int, int]] = set()

    def move(self) -> bool:
        dr = (-1, 0, 1, 0)[self.direction]
        dc = (0, 1, 0, -1)[self.direction]
        nr, nc = self.row + dr, 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, self.col = nr, nc
        return True

    def turn_left(self) -> None:
        self.direction = (self.direction + 3) % 4

    def turn_right(self) -> None:
        self.direction = (self.direction + 1) % 4

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


class Solution:
    # Time: O(m * n)
    # Space: O(m * n) visited set
    def clean_room(self, robot: Robot) -> None:
        deltas = ((-1, 0), (0, 1), (1, 0), (0, -1))
        visited: set[tuple[int, int]] = set()

        def go_back() -> None:
            robot.turn_right()
            robot.turn_right()
            robot.move()
            robot.turn_right()
            robot.turn_right()

        def backtrack(cell: tuple[int, int], direction: int) -> None:
            visited.add(cell)
            robot.clean()
            for k in range(4):
                nd = (direction + k) % 4
                ncell = (cell[0] + deltas[nd][0], cell[1] + deltas[nd][1])
                if ncell not in visited and robot.move():
                    backtrack(ncell, nd)
                    go_back()
                robot.turn_right()

        backtrack((0, 0), 0)
```

## Complexity

| Time | Space |
| - | - |
| O(m \* n) | O(m \* n) visited set |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.