Katkat
Back

Compute reachable cells for a cleaning robot

PinterestSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests graph traversal techniques (BFS/DFS) on a 2D grid, focusing on efficient coordinate management and state representation when navigating obstacles.

Problem Statement

You are developing software for a cleaning robot operating on a floor represented as a 2D grid of size M x N. The grid contains empty cells (0) and obstacles (1).

Given the starting coordinates (start_r, start_c) and a maximum movement limit k (the total number of steps the robot can take), calculate the total number of unique cells the robot can reach. The robot can move in 8 directions (horizontal, vertical, and diagonal). The robot cannot move through obstacles.

Function Signature

def count_reachable_cells(grid: List[List[int]], start: Tuple[int, int], k: int) -> int:

Constraints

  • 1 <= M, N <= 500
  • 0 <= k <= 10^5
  • grid[start_r][start_c] is always 0.

Example 1

Input:

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

Output: 4 Explanation: The robot can move from (0,0) to (0,1), (1,0), and (1,1) is blocked. Wait, with 8-way movement, the reachable cells are (0,0), (0,1), (1,0), and (1,1) is an obstacle. Only (0,1), (1,0), (0,0) are reachable.

Example 2

Input:

grid = [[0, 0], 
        [0, 0]], start = (0, 0), k = 2

Output: 4 Explanation: All cells are reachable within 2 steps.

Hints

Hint 1

Since this is an unweighted shortest path problem on a grid, consider using Breadth-First Search (BFS).

Hint 2

Use a set or a 2D boolean array to keep track of visited coordinates to prevent redundant processing.

Hint 3

Ensure the robot's movement logic correctly accounts for all 8 neighboring cells, including diagonals.

Follow-up questions

  • How would you modify the algorithm if the robot could remove up to one obstacle during its journey?
  • If there are two robots starting at different positions, how would you determine how many cells are reachable by at least one of them?
  • What is the time and space complexity of your BFS approach, and can it be optimized if k is significantly larger than the total number of cells?