2061. Number of Spaces Cleaning Robot Cleaned - Detailed Explanation

Problem Statement

You are given an m x n grid where:

• 0 represents a cleanable space.
• 1 represents an obstacle.

The robot is placed at a starting coordinate that is guaranteed to be on a cleanable cell. From its starting position, the robot can move one cell at a time in the four cardinal directions (up, down, left, right) and cleans the cell when it enters it. The robot cannot move into obstacles or outside the grid. Your task is to count how many unique spaces the robot can clean.

Example Inputs, Outputs, and Explanations

Example 1

Input:

grid = [
  [0, 0, 1],
  [0, 0, 0],
  [1, 0, 0]
]
start = (1, 1)

Output: 7
Explanation: Starting from (1,1), the robot can reach and clean the cells at positions: (1,1), (1,0), (1,2), (0,1), (0,0), (2,1), and (2,2).

Example 2

Input:

grid = [
  [0, 1, 1],
  [0, 0, 0],
  [1, 1, 0]
]
start = (1, 1)

Output: 5
Explanation: The robot cleans cells (1,1), (1,0), (1,2), (0,0), and (2,2). The obstacles block access to other cells.

Example 3

Input:

grid = [
  [1, 1, 1],
  [1, 0, 1],
  [1, 1, 1]
]
start = (1, 1)

Output: 1
Explanation: The robot starts in the only cleanable cell (1,1) and cannot move to any other cell due to surrounding obstacles.

Constraints

• The grid dimensions m and n are within a reasonable range (e.g., 1 ≤ m, n ≤ 100).
• The grid contains only the values 0 (free space) and 1 (obstacle).
• The starting position is always on a cell with 0.
• Movement is allowed only in the four directions: up, down, left, and right.

Hints

• Hint 1: Think about how you would explore a maze. A common approach is to use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse all reachable nodes (cells).
• Hint 2: Mark each visited cell to avoid re-cleaning or infinite loops. Consider using an auxiliary data structure (like a 2D boolean array) to track visited cells.
• Hint 3: Always check for boundaries and obstacles before moving to a new cell.

Approach Overview

There are two main approaches to solve this problem: DFS and BFS. Both methods can explore the connected component of free cells efficiently.

Depth-First Search (DFS)

Start at the robot’s initial position and use recursion to explore all adjacent cells that are cleanable (i.e., not obstacles and within bounds). Mark each visited cell to ensure it is not processed again.

Step-by-Step Walkthrough

• Initialize: Create a 2D array (of the same dimensions as the grid) to mark visited cells.
• Recursive Function: Define a function dfs(i, j) that:
  • Checks if the current cell (i, j) is out of bounds, is an obstacle, or has already been visited. If so, return 0.
  • Marks the cell as visited.
  • Cleans the cell (counts it as 1) and recursively calls dfs on its four adjacent cells.
  • Returns the total count of cleaned cells from this cell.
• Execution: Call dfs from the starting position and return the total count.

Visual Example

For the grid in Example 1, starting at (1,1):

• From (1,1), move to adjacent cells: (0,1), (1,0), (1,2), and (2,1).
• For each move, mark the cell as visited and continue exploring adjacent cells.
• The recursion backtracks when it reaches a boundary or an obstacle.

Breadth-First Search (BFS)

Use a queue to explore the grid level by level. This approach is similar to DFS in logic and also counts each unique cell exactly once.

Step-by-Step Walkthrough

• Initialize: Create a 2D boolean array for visited cells.
• Queue: Add the starting position to a queue.
• Process Queue: While the queue is not empty:

  • Dequeue a cell.

  • If the cell is valid (inside bounds, not an obstacle, and not visited), mark it as visited and increment the count.

  • Enqueue all valid adjacent cells.

• Completion: Continue until the queue is empty, then return the total count.

Both DFS and BFS run in O(m * n) time in the worst case since every cell is visited at most once.

Python Code