Simulate Threshold Infection Efficiently

Problem Statement

You are given an m x n grid of integers thresholds, where thresholds[r][c] represents the number of infected 4-directional neighbors cell (r, c) requires before it becomes infected. You are also given a list of coordinate pairs initially_infected, representing cells that are infected at round 0.

The infection spreads across the grid in synchronous rounds under the following rules:

1. Round 0: All cells in initially_infected become infected at round 0. Furthermore, any cell with thresholds[r][c] == 0 requires zero infected neighbors and also becomes infected at round 0.
2. Subsequent Rounds (t >= 1): In round t, any healthy cell that has accumulated at least thresholds[r][c] infected neighbors from rounds < t becomes infected at round t.
3. Once a cell is infected, it remains infected for all subsequent rounds and contributes toward infecting its adjacent neighbors.
4. Cells are 4-directionally adjacent (up, down, left, right).

Return an m x n grid infection_times, where infection_times[r][c] is the round number in which cell (r, c) became infected, or -1 if the cell is never infected.

Your solution should run in O(m * n) time and avoid repeatedly scanning the entire grid each round.

Function Signature

def get_infection_times(thresholds: list[list[int]], initially_infected: list[tuple[int, int]]) -> list[list[int]]:
    pass

Examples

Example 1

thresholds = [
    [2, 2, 2],
    [2, 2, 2],
    [2, 2, 2]
]
initially_infected = [(0, 0), (0, 2), (2, 0)]

# Output:
# [
#   [ 0,  1,  0],
#   [ 1,  2, -1],
#   [ 0, -1, -1]
# ]

Explanation:

• At round 0: (0, 0), (0, 2), and (2, 0) are infected.
• At round 1: Cell (0, 1) has two infected neighbors (0, 0) and (0, 2) (threshold 2), so it infects. Cell (1, 0) has two infected neighbors (0, 0) and (2, 0) (threshold 2), so it infects.
• At round 2: Cell (1, 1) now sees infected neighbors (0, 1) and (1, 0) (count reaches 2), so it infects.
• Cells (1, 2), (2, 1), and (2, 2) never reach 2 infected neighbors, so their value remains -1.

Example 2

thresholds = [
    [1, 0],
    [3, 1]
]
initially_infected = []

# Output:
# [
#   [ 1,  0],
#   [-1,  1]
# ]

Explanation:

• Cell (0, 1) has threshold 0, so it becomes infected at round 0 without needing any initial seeds.
• In round 1, its neighbors (0, 0) and (1, 1) both have threshold 1 and now have 1 infected neighbor, so both infect at round 1.
• Cell (1, 0) requires 3 neighbors, which it never reaches.

Constraints

• m == len(thresholds)
• n == len(thresholds[0])
• 1 <= m, n <= 1000
• m * n <= 10^6
• 0 <= thresholds[r][c] <= 4
• 0 <= len(initially_infected) <= m * n
• Coordinates in initially_infected are within bounds.