Threshold infection spread on a grid

A lab tracks a disease across a rectangular field of cells. You are given an m x n grid where 0 is a healthy cell and 1 is an infected cell, and an integer threshold.

Each day, all cells update at the same time, based on the grid as it was at the start of that day:

• A healthy cell becomes infected if at least threshold of its up to 8 neighbors (horizontal, vertical and diagonal) are infected.
• An infected cell stays infected forever.

The process stops on the first day when no new cell becomes infected.

Implement:

def spread(grid: list[list[int]], threshold: int) -> tuple[int, list[list[int]]]:
    ...

Return the number of days on which at least one cell became infected, and the final grid. Do not modify the input.

Constraints

• 0 <= m, n <= 1000
• 0 <= threshold <= 9. A threshold of 0 infects every healthy cell on day 1, and a threshold of 9 can never be met.

Example 1

grid = [[1, 0, 0, 0]], threshold = 1
day 1: [[1, 1, 0, 0]]
day 2: [[1, 1, 1, 0]]
day 3: [[1, 1, 1, 1]]
-> (3, [[1, 1, 1, 1]])

Updates are simultaneous: the cell infected on day 1 does not help its neighbor on that same day.

Example 2

grid = [[1, 0, 0],
        [0, 0, 0],
        [0, 0, 1]], threshold = 2
day 1: only the center sees two infected neighbors
day 2: the four edge cells each see a seed plus the center
day 3: the last two corners see three infected neighbors each
-> (3, all ones)

Aim for better than re-scanning the whole grid every day.