⚡Flashcard Drill➔
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

  1. This is a DFS on an implicit grid, with the robot's absolute position tracked by the algorithm rather than reported by the API.
  2. Keep a visited set of absolute coordinates, and a direction index for the robot's current heading.
  3. 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.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems