Robot Room Cleaner
Hard · Backtracking · Backtracking · Interactive
Problem
A cleaning robot stands somewhere in a room you cannot see. The room is a grid of cells, each open or a wall, and everything outside the grid counts as wall. The robot starts on an open cell, facing up, and every open cell can be reached from it.
You control the robot only through its interface:
- robot.move() steps one cell forward and returns True, or returns False and stays put if a wall is ahead;
- robot.turnLeft() and robot.turnRight() turn it 90 degrees where it stands;
- robot.clean() cleans the cell it stands on.
You never learn the grid or the robot's coordinates. Implement cleanRoom(robot) so that every open cell gets cleaned.
For testing, the judge builds the robot from room (1 = open, 0 = wall) and the start row, col, runs your function, and returns the open cells left dirty: [] means the room is clean.
Examples
Input: room = [[1,1,0],[1,1,1]], row = 0, col = 0 Output: []
A depth-first walk that steps back by turning around reaches and cleans all 5 open cells, so no cell is left dirty.
Input: room = [[0,1,0],[1,1,1],[0,1,0]], row = 1, col = 1 Output: []
From the center the robot visits each arm of the plus and comes back: 5 cells cleaned.
Input: room = [[1,1,1,1,1]], row = 0, col = 2 Output: []
Up and down are walls. The robot cleans the corridor to one end, comes back, and cleans the other end.
Constraints
- 1 <= len(room), len(room[0]) <= 100
- room[i][j] is 0 or 1
- room[row][col] == 1
- every open cell is connected to the start
Approaches
- Walk to the nearest unexplored cell each time — time O(N²), space O(N)
Follow-up
The depth-first walk moves along each edge of its search tree twice, so it makes about 2N moves for N open cells. Can it do better? Not in general: in a tree-shaped room, every corridor has to be walked in and out. What it can avoid is re-probing: marking walls as seen, as the solution does, saves a turn-and-bump on every second look at the same wall.
Related problems
Start free on Cariara · Coding problems · System design studio
