Compute time to infect all cells

You are given an n × m grid representing people in a city.

• Each cell is either infected ( 1 ) or healthy ( 0 ).
• Two cells are neighbors if they share an edge (4-directional: up/down/left/right).
• Infection spreads in discrete time steps (t = 0, 1, 2, ...).
• At each time step, all updates happen simultaneously :
  • Any healthy cell becomes infected at the next step if it currently has at least K infected neighbors .
  • Infected cells stay infected.

Task

Return the minimum number of time steps until all cells are infected.

• If the grid is already fully infected, return 0 .
• If it is impossible for all cells to become infected, return -1 .

Input

• grid : an n × m matrix of 0/1
• K : an integer threshold ( 0 ≤ K ≤ 4 )

Output

• An integer: minimum time steps to infect all cells, or -1 if impossible.

Notes / Edge cases

• If K = 0 , then all healthy cells become infected after 1 step (unless already all infected).
• A cell on the border has fewer than 4 neighbors.

(Assume 1 ≤ n, m ≤ 200 and aim for an efficient solution.)