The Question
CodingRobot 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.