Compute time for virus to infect grid

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.