Spreading Contagion on a Grid

Spreading Contagion on a Grid

You are monitoring a cluster of compute nodes arranged in an m x n grid. A security exploit has compromised some nodes, and the contagion is spreading across adjacent nodes at regular discrete time intervals.

Each cell in the grid has one of three possible states:

• 0: Inactive / empty cell (cannot be infected or transmit the contagion).
• 1: Susceptible node (currently healthy, but vulnerable).
• 2: Infected node (compromised and actively spreading).

Every minute, any susceptible node (1) that shares an edge (up, down, left, right) with at least one infected node (2) becomes infected.

Write a function to determine the minimum number of minutes that must elapse until no susceptible nodes remain in the grid. If it is impossible to infect all susceptible nodes (i.e., some susceptible nodes can never be reached), return -1.

Function Signature

def min_spread_time(grid: list[list[int]]) -> int:
    pass

Constraints

• m == len(grid)
• n == len(grid[i])
• 1 <= m, n <= 100
• grid[r][c] is either 0, 1, or 2.

Examples

Example 1:

Input: grid = [
  [2, 1, 1],
  [1, 1, 0],
  [0, 1, 1]
]
Output: 4
Explanation:
- Minute 0: Infected at (0, 0)
- Minute 1: (0, 1) and (1, 0) become infected
- Minute 2: (0, 2) and (1, 1) become infected
- Minute 3: (2, 1) becomes infected
- Minute 4: (2, 2) becomes infected
All susceptible nodes are infected after 4 minutes.

Example 2:

Input: grid = [
  [2, 1, 0],
  [0, 0, 0],
  [1, 1, 1]
]
Output: -1
Explanation: The nodes in the bottom row cannot be reached by the infection because the middle row consists entirely of inactive cells.

Example 3:

Input: grid = [
  [0, 2]
]
Output: 0
Explanation: There are no susceptible nodes initially, so the process finishes in 0 minutes.

Edge Cases to Consider

• Grids containing no susceptible nodes (1) initially should immediately return 0.
• Grids with susceptible nodes but no infected nodes (2) should return -1.
• Disconnected components separated by inactive cells (0).