You are given an m x n grid representing the state of individuals in a lab.
-
0
= empty cell (no one)
-
1
= healthy individual
-
2
= infected individual
Every minute, any healthy individual (1) that is 4-directionally adjacent (up/down/left/right) to an infected individual (2) becomes infected.
Return the minimum number of minutes needed until no healthy individuals remain. If it is impossible to infect all healthy individuals, return -1. If there are no healthy individuals initially, return 0.
Input
-
A 2D integer array
grid
of size
m x n
.
Output
-
An integer: the minimum minutes to infect everyone, or
-1
if impossible.
Constraints
-
1 ≤ m, n ≤ 200
-
grid[i][j] ∈ {0,1,2}
Notes (as in the interview)
-
You may be asked to write your own test cases (including edge cases) to validate your solution.