Infection Spread on a Grid (Cellular Automaton)

Problem Statement

You are tasked with modeling the spread of a virus across a 2D grid of size m x n. Each cell in the grid can initially be in one of three states:

• 0: Susceptible (can be infected)
• 1: Infected (freshly infected at time t = 0)
• -1: Barrier (impassable; cannot be infected or transmit infection)

The simulation proceeds in discrete, synchronous time steps (t = 1, 2, 3, ...). At each time step, state transitions occur simultaneously according to the following rules:

1. Infection Spread: A susceptible cell (0) becomes infected at the start of step t if and only if it shares an edge (up, down, left, right) with at least threshold currently infected cells.
2. Recovery: An infected cell remains active for exactly duration steps. After being active for duration steps, it recovers and becomes immune. Once immune, a cell cannot be infected again and cannot infect others.

The simulation stops when there are no longer any actively infected cells remaining on the grid.

Write a function simulate_infection(grid: list[list[int]], duration: int, threshold: int) -> int that returns the total number of elapsed time steps until the simulation terminates (i.e., when 0 infected cells remain).

Function Signature

def simulate_infection(grid: list[list[int]], duration: int, threshold: int) -> int:
    pass

Examples

Example 1

grid = [
    [0, 1, 0],
    [0, 0, 0],
    [0, 0, 0]
]
duration = 2
threshold = 1

Output: 5

Explanation:

• t = 0: Active infected at (0, 1) with 2 steps left.
• t = 1: (0, 1) has 1 step left. It infects (0, 0), (0, 2), and (1, 1). Active: (0, 1) [left: 1], (0, 0) [left: 2], (0, 2) [left: 2], (1, 1) [left: 2].
• t = 2: (0, 1) recovers (immune). The new infected cells infect (1, 0), (1, 2), (2, 1). Active cells decrement.
• Propagations continue until all reachable cells are infected and their duration expires, finishing at t = 5.

Example 2

grid = [
    [1, 0, 0],
    [0, -1, 0],
    [0, 0, 0]
]
duration = 3
threshold = 2

Output: 3

Explanation: Because threshold = 2, the single infected cell at (0, 0) cannot infect any neighbor by itself. It remains infected for 3 steps and then recovers. At t = 3, 0 infected cells remain.

Constraints

• 1 <= m, n <= 250
• grid[r][c] is one of {-1, 0, 1}
• 1 <= duration <= 100
• 1 <= threshold <= 4