Minutes Until Spoilage Spreads to Every Fresh Item in a Grid

A storage grid holds perishable items. Each cell is empty (`0`), holds a fresh item (`1`), or holds a spoiled item (`2`). Every minute, each fresh item that shares an edge with a spoiled item becomes spoiled. Return the number of minutes that pass until no fresh item remains, or `-1` if some fresh item can never spoil. ### Function Signature ```python def minutes_until_all_spoiled(grid: list[list[int]]) -> int: ``` ### Rules - Two cells share an edge when they are next to each other horizontally or vertically; diagonal cells do not share an edge. - Spreading is simultaneous: an item that spoils during minute `t` starts spoiling its neighbors only during minute `t + 1`. - If the grid contains no fresh item at the start, return `0`. - If some fresh item can never become spoiled, return `-1`. - Otherwise, return the smallest number of minutes after which no cell holds a fresh item. ### Constraints - `1 <= len(grid) <= 500` and `1 <= len(grid[0]) <= 500`; every row has the same length. - Every `grid[r][c]` is `0`, `1` or `2`. ### Examples **Example 1** ```text Input: grid = [[2, 1, 0], [1, 1, 0], [0, 1, 1]] Output: 4 ``` Minute 1 spoils the items at `(0, 1)` and `(1, 0)`, minute 2 the item at `(1, 1)`, minute 3 the item at `(2, 1)`, and minute 4 the item at `(2, 2)`. **Example 2** ```text Input: grid = [[2, 1, 1, 1, 2]] Output: 2 ``` Both spoiled items spread at once: minute 1 spoils `(0, 1)` and `(0, 3)`, and minute 2 spoils `(0, 2)`. **Example 3** ```text Input: grid = [[1, 0, 2]] Output: -1 ``` The fresh item at `(0, 0)` has only the empty cell `(0, 1)` as a neighbor, so it never spoils.