NeetCode #522LC-489HardBacktracking
← Back to All Problems#522 · #489 · Robot Room Cleaner(扫地机器人)
📌 Problem Statement & Constraints
This is an interactive problem. A robot can
move() (returns whether the move succeeded), turnLeft(), turnRight() and clean(). Given only its API, clean an entire room. The room is a grid with obstacles, and the robot starts somewhere facing up. Constraints: the room is at most 1000 cells; the robot's start position is unknown to you.💡 Core Algorithmic Approaches
- This is a DFS on an implicit grid, with the robot's absolute position tracked by the algorithm rather than reported by the API.
- Keep a
visitedset of absolute coordinates, and a direction index for the robot's current heading. - For each of the four directions: turn to it, and if the target cell is unvisited and
move()succeeds, recurse and then return to the previous cell. - Returning requires two right turns, a move, and two more right turns -- restoring both position and heading.
💻 Benchmark Python3 Implementation
class Solution:
def cleanRoom(self, robot: "Robot") -> None:
# absolute directions: up, right, down, left
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
visited = set()
def go_back() -> None:
robot.turnRight()
robot.turnRight()
robot.move() # step back
robot.turnRight()
robot.turnRight() # restore the heading
def dfs(r: int, c: int, d: int) -> None:
visited.add((r, c))
robot.clean()
for i in range(4): # try all four headings
nd = (d + i) % 4
nr, nc = r + dirs[nd][0], c + dirs[nd][1]
if (nr, nc) not in visited and robot.move():
dfs(nr, nc, nd)
go_back() # return to (r, c) with heading d
robot.turnRight() # face the next candidate direction
dfs(0, 0, 0)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(number of cells): each cell is cleaned once and each edge is traversed a constant number of times.
💾 Space Complexity
O(number of cells) for the visited set plus the recursion depth.
⚠️ Interview Pitfalls & Follow-ups
- Tracking only relative movements: the robot's absolute position must be maintained by the algorithm, since the API does not report it.
- Forgetting to restore the heading after returning: subsequent direction trials would be wrong.
- Calling
clean()before marking visited: it would be cleaned repeatedly. - Trying
move()without checking the visited set: the robot would revisit cells and possibly loop. - Assuming the room is rectangular and aligned with the start: the DFS with absolute coordinates handles arbitrary obstacles.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.