Given an `n x m` grid representing people in a city, simulate how an infection spreads and return the **minimum number of time steps until every cell is infected**. ## Input - `grid`: an `n x m` 2D array where each cell is either: - `1` — **infected**, or - `0` — **healthy**. - `K`: an integer threshold (the number of infected neighbors required to infect a healthy cell). Two cells are **neighbors** if they share an edge (up, down, left, or right). Diagonal cells are *not* neighbors. ## How the infection spreads Infection spreads in discrete time steps `t = 0, 1, 2, ...`. At each step, **all updates happen simultaneously**: - A **healthy** cell becomes infected at the next step if it currently has **at least `K` infected neighbors**. - Once **infected**, a cell stays infected forever. > **Simultaneity rule:** because updates apply at the same instant, a cell that becomes infected at time `t` cannot help infect its own neighbors until time `t + 1`. ## What to return Implement: ```python def solution(grid, K): ``` Return the **minimum number of time steps** needed for every cell in the grid to be infected, subject to these rules: - If the grid is **already fully infected**, return `0`. - If it is **impossible** for all cells to eventually become infected, return `-1`. - **Special case `K = 0`:** every healthy cell becomes infected after exactly `1` step. So return `1` whenever the grid contains at least one healthy cell, and `0` if the grid is already fully infected. (This holds even if there are no initially infected cells.) ## Constraints - `1 <= n, m <= 200` - `grid[i][j]` is either `0` or `1` - `0 <= K <= 4` ## Examples - `grid = [[1,0,0],[0,0,0]]`, `K = 1` → `3` (infection radiates outward one ring per step). - `grid = [[1,1],[1,1]]`, `K = 3` → `0` (already fully infected). - `grid = [[0,0],[0,0]]`, `K = 1` → `-1` (no infected cells and `K >= 1`, so nothing can ever spread). - `grid = [[0,0,0],[0,0,0]]`, `K = 0` → `1` (with `K = 0`, every healthy cell flips after one step).