Google | Onsite | Robot Room Cleaner

You are controlling a robot that is placed in a room. The room is represented as a grid where each cell can be either empty or blocked. The robot can move in four directions: up, down, left, or right. It can also clean the cell it’s currently on.

The robot starts in an arbitrary cell and can move freely. Your task is to design an algorithm to clean the entire room using the robot.

Input:

• The robot API interface with the following methods:
• robot.move(): Moves the robot to the next cell.
• robot.turnLeft(): Turns the robot 90 degrees to the left.
• robot.turnRight(): Turns the robot 90 degrees to the right.
• robot.clean(): Cleans the current cell.

Constraints:

• The room is guaranteed to be a rectangular grid.
• The robot can move to any cell (empty or blocked).
• The robot will not move outside the room.
• The robot can turn left or right without restriction.

Example:

Suppose the room is represented as a 2D grid, where 0 represents an empty cell and 1 represents a blocked cell:

[
 [1, 1, 1, 1, 1],
 [1, 0, 0, 0, 1],
 [1, 0, 1, 0, 1],
 [1, 0, 0, 0, 1],
 [1, 1, 1, 1, 1]
]

The robot starts at position (1, 1) facing up. It can perform the following actions:

1. Clean the current cell.
2. Move to the right.
3. Clean the current cell.
4. Turn right.
5. Move to the down.
6. Clean the current cell.
7. Turn right.
8. Move to the left.
9. Clean the current cell.
10. Turn right.
11. Move to the up.
12. The robot has now cleaned the entire room.