Problem Description

You have a 2D grid representing a room where:

• 0 represents an empty space
• 1 represents an obstacle/object
• The top-left corner (0, 0) is always empty

A cleaning robot starts at position (0, 0) facing right and follows these rules:

1. The robot moves straight in its current direction until it either:
   • Hits the edge of the room, OR
   • Encounters an obstacle (a cell with value 1)
2. When the robot can't move forward, it turns 90 degrees clockwise and continues
3. Every cell the robot visits (including the starting cell) gets cleaned

The robot continues this process indefinitely. Since the robot follows a deterministic pattern, it will eventually enter a cycle and repeat its path.

Your task is to determine the total number of unique cells that get cleaned by the robot.

Example behavior:

• Robot starts at (0, 0) facing right (east)
• If it hits a wall or obstacle while moving right, it turns to face down (south)
• If it hits a wall or obstacle while moving down, it turns to face left (west)
• If it hits a wall or obstacle while moving left, it turns to face up (north)
• If it hits a wall or obstacle while moving up, it turns to face right (east) again

The solution uses DFS to simulate the robot's movement, tracking visited states as (row, column, direction) tuples. When the robot reaches a state it has seen before, it has entered a cycle and will not clean any new cells. The algorithm counts all unique cells visited before entering the cycle.

Intuition

The key insight is that the robot follows a completely deterministic path - given its current position and direction, its next move is always predictable. This means the robot will eventually revisit a state it's been in before (a combination of position and direction), creating a cycle.

Think of it this way: the room is finite, and the robot can only face 4 directions. So there are at most rows × columns × 4 possible states. Since the robot moves deterministically, once it revisits any state (row, col, direction), it will repeat the exact same sequence of moves it made from that state previously, entering an infinite loop.

The challenge becomes: how do we detect when the robot enters this cycle? We need to track not just which cells we've visited, but also the direction we were facing when we visited them. This is crucial because visiting cell (2, 3) while facing right leads to a different next move than visiting (2, 3) while facing down.

Once we detect a repeated state (same position AND same direction), we know:

1. The robot has entered a cycle
2. No new cells will be cleaned from this point forward
3. We can stop the simulation

The simulation approach naturally emerges from this understanding:

• Track states as (row, column, direction) tuples
• Simulate the robot's movement according to the rules
• Mark each new cell we visit as cleaned (but only count it once even if visited multiple times)
• Stop when we encounter a state we've seen before

Using DFS to implement this is natural because we're essentially exploring a path through the state space until we hit a cycle. The recursive nature of DFS makes it easy to handle the two cases: either continue straight or turn clockwise when blocked.

Solution Approach

The solution uses a depth-first search (DFS) to simulate the robot's movement through the room. Here's how the implementation works:

Data Structures:

• vis: A set to store visited states as (row, column, direction) tuples to detect cycles
• dirs: A tuple (0, 1, 0, -1, 0) that encodes the four directions. Each consecutive pair represents a direction vector: right (0, 1), down (1, 0), left (0, -1), up (-1, 0)
• ans: Counter for the number of cleaned cells

Algorithm Flow:

1. State Tracking: The DFS function dfs(i, j, k) takes three parameters:

   • i, j: Current position of the robot
   • k: Current direction index (0=right, 1=down, 2=left, 3=up)

2. Cycle Detection:

   if (i, j, k) in vis:
       return

   If we've seen this exact state before, we've entered a cycle and stop the simulation.

3. Cell Cleaning:

   ans += room[i][j] == 0
   room[i][j] = -1

   • Count the cell if it's currently empty (value 0)
   • Mark it as -1 to indicate it's been cleaned (avoiding double-counting)

4. State Recording:

   vis.add((i, j, k))

   Add the current state to our visited set.

5. Movement Logic:

   x, y = i + dirs[k], j + dirs[k + 1]

   Calculate the next position based on current direction. The dirs array is cleverly structured so that dirs[k] gives the row offset and dirs[k + 1] gives the column offset for direction k.

6. Decision Making:

   if 0 <= x < len(room) and 0 <= y < len(room[0]) and room[x][y] != 1:
       dfs(x, y, k)  # Continue straight
   else:
       dfs(i, j, (k + 1) % 4)  # Turn clockwise

   • If the next position is valid (within bounds) and not an obstacle (!= 1), move there
   • Otherwise, stay in place but turn 90 degrees clockwise by incrementing the direction index modulo 4

The algorithm starts with dfs(0, 0, 0) (top-left corner, facing right) and continues until it detects a cycle, at which point it returns the total count of cleaned cells.

Example Walkthrough

Let's trace through a small example to illustrate how the solution works:

Grid:

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

Step-by-step simulation:

1. Start: Robot at (0,0), facing right (direction=0)

   • State: (0,0,0) - not visited yet, add to vis
   • Cell is empty (0), so ans = 1
   • Mark cell as cleaned: room[0][0] = -1
   • Next position would be (0,1) - valid and not obstacle
   • Move to (0,1)

2. Position (0,1), facing right (direction=0)

   • State: (0,1,0) - not visited yet, add to vis
   • Cell is empty (0), so ans = 2
   • Mark cell as cleaned: room[0][1] = -1
   • Next position would be (0,2) - it's an obstacle (1)!
   • Can't move forward, turn clockwise to face down (direction=1)

3. Position (0,1), facing down (direction=1)

   • State: (0,1,1) - not visited yet, add to vis
   • Cell already cleaned (-1), so ans stays 2
   • Next position would be (1,1) - it's an obstacle (1)!
   • Can't move forward, turn clockwise to face left (direction=2)

4. Position (0,1), facing left (direction=2)

   • State: (0,1,2) - not visited yet, add to vis
   • Cell already cleaned (-1), so ans stays 2
   • Next position would be (0,0) - valid and not obstacle
   • Move to (0,0)

5. Position (0,0), facing left (direction=2)

   • State: (0,0,2) - not visited yet, add to vis
   • Cell already cleaned (-1), so ans stays 2
   • Next position would be (0,-1) - out of bounds!
   • Can't move forward, turn clockwise to face up (direction=3)

6. Position (0,0), facing up (direction=3)

   • State: (0,0,3) - not visited yet, add to vis
   • Cell already cleaned (-1), so ans stays 2
   • Next position would be (-1,0) - out of bounds!
   • Can't move forward, turn clockwise to face right (direction=0)

7. Position (0,0), facing right (direction=0)

   • State: (0,0,0) - Already visited! (We saw this in step 1)
   • Cycle detected - stop simulation

Result: The robot cleaned 2 unique cells: (0,0) and (0,1)

The key insight demonstrated here is that we track states as (row, col, direction) tuples. Even though the robot visited position (0,0) multiple times (steps 1, 5, 6, 7), it was facing different directions in steps 5 and 6, so those were new states. Only when it returned to (0,0) facing right again in step 7 did we detect the cycle, because that exact state (0,0,0) was already in our visited set.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n * 4) = O(m * n) where m is the number of rows and n is the number of columns in the room.

The algorithm uses DFS to simulate a robot cleaning rooms. The robot can be in any cell facing one of 4 directions (right, down, left, up). The key insight is that each state (i, j, k) where i is row, j is column, and k is direction (0-3) can be visited at most once due to the visited set vis. Since there are m * n cells and 4 possible directions for each cell, the maximum number of states is m * n * 4. Each state is processed in O(1) time, giving us O(m * n * 4) = O(m * n) time complexity.

Space Complexity: O(m * n)

The space complexity consists of:

• The visited set vis which can store at most m * n * 4 states, contributing O(m * n) space
• The recursion stack depth which in the worst case can go up to O(m * n) when the robot visits all cells before entering a cycle
• The room matrix is modified in-place (cells are marked as -1 when cleaned), so no additional space is used for this

Therefore, the overall space complexity is O(m * n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Double-counting cleaned cells

Problem: A major pitfall is counting the same cell multiple times when the robot revisits it. Since the robot can pass through the same cell multiple times (potentially from different directions), naive implementations might increment the counter each time.

Example scenario:

# WRONG: This counts the cell every time it's visited
def dfs(row, col, direction):
    if (row, col, direction) in visited_states:
        return
    cleaned_count += 1  # This counts revisited cells multiple times!
    visited_states.add((row, col, direction))
    # ... rest of logic

Solution: Mark cells as cleaned by changing their value to a sentinel value (like -1) and only count cells that still have value 0:

# CORRECT: Only count unvisited clean rooms
if room[row][col] == 0:
    cleaned_count += 1
    room[row][col] = -1  # Mark as visited

2. Confusing state vs. position in cycle detection

Problem: Using only position (row, col) for cycle detection instead of the complete state (row, col, direction). The robot entering the same cell from a different direction is NOT a cycle.

Example scenario:

# WRONG: This stops too early
if (row, col) in visited_states:  # Missing direction!
    return
visited_states.add((row, col))  # Incomplete state

Solution: Always track the complete state including direction:

# CORRECT: Full state tracking
if (row, col, direction) in visited_states:
    return
visited_states.add((row, col, direction))

3. Incorrect direction encoding or rotation

Problem: The directions array uses a clever encoding where consecutive elements form coordinate pairs. Misunderstanding this can lead to incorrect movement calculations.

Common mistakes:

• Using separate arrays for dx and dy
• Incorrect modulo arithmetic for rotation
• Wrong index access for direction vectors

Example scenario:

# WRONG: Incorrect direction access
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
next_row = row + dx[direction]
next_col = col + dy[direction]

# WRONG: Counter-clockwise rotation instead of clockwise
new_direction = (direction - 1) % 4  # This rotates counter-clockwise!

Solution: Use the compact encoding correctly:

# CORRECT: Single array with paired elements
directions = (0, 1, 0, -1, 0)
next_row = row + directions[direction]
next_col = col + directions[direction + 1]

# CORRECT: Clockwise rotation
new_direction = (direction + 1) % 4

4. Modifying the input array without considering side effects

Problem: The solution modifies the input room array by marking visited cells as -1. This could be problematic if:

• The original array needs to be preserved
• Multiple test cases use the same array
• The caller expects the array to remain unchanged

Solution: Create a copy of the room or use a separate data structure to track cleaned cells:

# Alternative approach without modifying input
cleaned_cells = set()

def dfs(row, col, direction):
    if (row, col, direction) in visited_states:
        return
  
    # Use a set to track cleaned cells instead of modifying the array
    if room[row][col] == 0 and (row, col) not in cleaned_cells:
        cleaned_cells.add((row, col))
  
    visited_states.add((row, col, direction))
    # ... rest of logic

# Return the size of cleaned_cells set
return len(cleaned_cells)