The Question
Coding

Robot Room Cleaner

Given a robot in an unknown grid that can move, turn, and clean, design an algorithm using only the robot's API to clean all reachable empty cells.
Java
DFS
Backtracking
HashSet
Questions & Insights

Thinking Process

Exploration Strategy: Since the robot's location and the room's dimensions are unknown, use Depth First Search (DFS) to explore and clean all reachable cells.
Coordinate System: Establish a virtual coordinate system starting at (0, 0) for the robot's initial position, using a Set to track visited coordinates and prevent infinite loops.
Physical Backtracking: Because the robot physically moves through the grid, every recursive DFS call must be followed by a manual "backtrack" move (turn 180^\circ, move, turn 180^\circ back) to restore the robot's state for the previous stack frame.
Directional Logic: Use a fixed array for directions (e.g., Up, Right, Down, Left) and maintain the robot's current facing direction to map virtual movements to the Robot API.
Implementation Breakdown

Problem Set

Functional Requirements: Clean all reachable empty slots (1s) in a grid of unknown size.
Constraints:
Robot starts at an unknown empty cell facing Up.
Grid is surrounded by walls.
Only API access: move(), turnLeft(), turnRight(), clean().
No direct grid access.

Approach

Algorithm: Depth First Search (DFS) with backtracking.
Data Structure: HashSet<String> to store visited row + "," + col coordinates.
Complexity:
Time: O(N - W) where N is the total cells and W is the number of walls (we visit each empty cell once).
Space: O(N - W) to store the visited set and recursion stack.

Implementation