Days Until Poison Stops Spreading in a Plant Grid Under a K-of-8-Neighbors Rule

A field of plants is laid out as an `m x n` grid. A cell holding `0` is a healthy plant and a cell holding `1` is a poisoned plant. Poison spreads once a day: on each day, every healthy plant that has at least `k` poisoned plants among its up to eight neighbors (left, right, up, down and the four diagonals) becomes poisoned. A poisoned plant stays poisoned. Return the number of days it takes for the field to become stable, that is, the number of days on which at least one plant becomes poisoned. ### Function Signature ```python def days_until_stable(grid: list[list[int]], k: int) -> int: ``` ### Rules - All plants update at the same time. Whether a healthy plant becomes poisoned on day `d` depends only on the grid as it was at the start of day `d`, so a plant poisoned on day `d` first counts toward its neighbors on day `d + 1`. - The threshold is inclusive: a healthy plant with exactly `k` poisoned neighbors becomes poisoned. - Cells outside the grid are not neighbors, so a plant on an edge or in a corner has fewer than eight neighbors. - Once a day passes on which no plant becomes poisoned, the grid never changes again. The days with new poisonings are therefore days `1, 2, ..., D`, and the answer is `D`. Return `0` if no plant ever becomes poisoned. ### Constraints - `1 <= m, n <= 500`, where `m = len(grid)` and `n = len(grid[0])`; every row has length `n`. - Every `grid[i][j]` is `0` or `1`. - `1 <= k <= 8` - The number of days can grow in proportion to `m * n`. Aim for `O(m * n)` total time rather than time proportional to the number of cells multiplied by the number of days. ### Examples **Example 1** ```text Input: grid = [[1, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]], k = 2 Output: 4 ``` The grid at the start and after each day: ```text start after day 1 after day 2 after day 3 after day 4 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 ``` On day 1, the plants at row 1, columns 0 and 1, each have two poisoned neighbors. On day 2, the plant at row 2, column 2 has only one poisoned neighbor (row 1, column 1), because its other neighbors are poisoned during that same day; it is poisoned on day 3. The plant at row 2, column 3 is poisoned last, on day 4, and day 5 poisons nothing. **Example 2** ```text Input: grid = [[1, 1, 0], [1, 0, 0], [0, 0, 0]], k = 3 Output: 1 ``` On day 1 the center plant has three poisoned neighbors and becomes poisoned. After that, every remaining healthy plant has at most two poisoned neighbors (the top-right plant, for example, touches only the top-middle and center plants), so nothing else changes and five plants stay healthy. **Example 3** ```text Input: grid = [[0, 0], [0, 0]], k = 1 Output: 0 ``` No plant is poisoned, so the poison never spreads.