Robot room cleaner: clean an unseen grid through a robot API

A cleaning robot is placed in an unknown room laid out as a grid with obstacles. You cannot see the room, its size, or the robot's position. Using only the robot's API, clean every cell the robot can reach.

Interface

Unless you agree on a different interface with the interviewer, assume:

• robot.move() -> bool — steps one cell forward. Returns False and stays put if an obstacle or wall is in front.
• robot.turn_left() -> None and robot.turn_right() -> None — turn 90 degrees in place.
• robot.clean() -> None — cleans the current cell.
• clean_room(robot) -> None — cleans every reachable cell. The robot starts facing up, on an open cell.

Example

1 = open, 0 = obstacle; the robot starts at row 1, column 3, facing up
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

clean_room(robot)   ->  all 30 open cells end up cleaned

Your code never sees this grid. It only learns where obstacles are when move() returns False.

Constraints

• The room is at most 100 x 100. All open cells reachable from the start are connected through their four sides.

Clarifying questions

• Does the robot need to return to its starting cell at the end?
• Is there a cost per API call, so needless moves should be avoided?
• Can cleaning a cell twice cause harm, or is it only wasted time?

What a strong answer covers

• Coordinates relative to the start, (0, 0) facing up, and a visited set of those coordinates.
• DFS: clean the cell, then try the four directions by turning right each time. Recurse into new open cells, and afterwards step back: turn around, move, turn around again to restore the heading.
• Keeping the tracked direction in step with every turn, so the coordinates stay correct.
• O(V) moves and O(V) memory for V reachable cells.
• Testing with a simulated robot over a known grid and checking every open cell was cleaned.

Follow-ups

• Return the robot to its starting cell and heading when it is done.
• Write it without recursion.
• The room has a charging dock. Find it and report the shortest route back from anywhere.