Cleaning Robot Reachable Cells
Medium · Graphs · Array · Matrix · Simulation
Problem
A cleaning robot moves around a room given as an m x n binary matrix room, where 0 is an empty cell and 1 is an obstacle. The robot starts in the top-left cell, which is always empty, facing right.
The robot always drives straight ahead. Whenever the next cell is outside the room or holds an obstacle, it turns 90 degrees clockwise instead of moving, then tries again. Every empty cell the robot stands on, including its starting cell, becomes clean.
The robot runs forever. Return how many distinct cells end up clean.
Examples
Input: room = [[0,0,0],[1,1,0],[0,0,0]] Output: 7
The robot sweeps the top row, the right column and the bottom row, then shuttles along the bottom row.
Input: room = [[0,1],[0,0]] Output: 2
It shuttles between the two left cells: at the bottom it faces the edge, turns left, then up, so the bottom-right cell is never reached.
Input: room = [[0,0,0],[0,0,0],[0,0,0]] Output: 8
It circles the border forever and never reaches the center.
Constraints
- m == len(room)
- n == len(room[r])
- 1 <= m, n <= 300
- room[r][c] is 0 or 1
- room[0][0] == 0
Approaches
- Simulate a fixed budget of 4mn actions — time O(m * n), space O(m * n)
Follow-up
The key is that the full state is (cell, facing), not just the cell: the robot can pass a cell facing one way and later face another. The use cases stop the robot after k actions (with k up to 10^9) and count only the cells on the loop it settles into.
Related problems
Start free on Cariara · Coding problems · System design studio
