Biological Hazards - Grid Simulation of Contamination Spread

Question

## Round 1 - Coding

## Problem

You are given a 2D grid representing a facility. Each cell is one of: `0` (empty/safe), `1` (contaminated), or `2` (blocked/wall). Each minute, contamination spreads from contaminated cells to all orthogonally adjacent safe cells. Blocked cells cannot be contaminated. Given the initial grid, return the number of minutes until all reachable cells are contaminated, or `-1` if some safe cells can never be reached.

```python
def time_to_contaminate(grid: list[list[int]]) -> int:
    # 0 = safe, 1 = contaminated, 2 = blocked
    # Returns minutes to fully contaminate all reachable safe cells,
    # or -1 if any safe cell is permanently isolated.
    ...
```

```
Example:
grid = [
    [2, 1, 0, 0],
    [0, 0, 0, 2],
    [0, 2, 0, 0],
    [0, 0, 1, 2],
]
time_to_contaminate(grid) -> 4
```

## Follow-ups

1. This is a multi-source BFS - why does BFS give the correct minimum time here?
2. How do you efficiently determine if any safe cell is permanently isolated after BFS completes?
3. What if contamination spreads diagonally as well - how does your solution change?
4. How would you extend this to 3D (a multi-floor building)?

Biological Hazards - Grid Simulation of Contamination Spread

Question Details

Full Details

Topics

More from OpenAI