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. Topics: Backtracking, Interactive. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 14 parametrized pytest cases, and a playground notebook:

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

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, full suite in test_solution.py:

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.