Problem Brief

Virus Spread (Intuit India)

INTERNOA

You are given a petri dish with a grid with some healthy cells at locations i,j. It is of dimensions N x M, where each grid point in the dish can only have the following values:

0: Empty

1: Has a healthy cell

2: Has a virus cell

Unfortunately, a virus can make its healthy neighbors sick (infected), and you need to find the minimum time at which all the cells have the virus. A virus-cell at location [i, j] will infect healthy cells at [i-1, j], [i+1, j], [i, j-1], [i, j+1] (up, down, left and right), and this takes place in one second of time. If not all cells in the dish are infected with the virus, then return -1.

Function Description

Complete the function minimumTimeToInfect in the editor.

minimumTimeToInfect has the following parameter:

int N: Num of rows

int M: Num of columns

N lines of the input contains the M space-separeted elements that indicate elements in each row of the matrix

Returns

int: an integer that denotes the min time for all cells to have the virus, or print -1 if not all cells in the dish are infected.

1Example 1

Input

N = 2, M = 3, grid = [[2, 0, 0], [1, 1, 1]]

Output

Explanation

The virus cell at (0,1) will infect the healthy cell at (0,0) after one second. After the second, the virus in (0,0) will infect the healthy cell at (1,0), and after the third second, the healthy cell in the lower right will be infected.

2Example 2

Input

N = 2, M = 3, grid = [[2, 0, 1], [1, 1, 0]]

Output

-1

Explanation

The healthy cell in the top right will not be infected since it is surrounded by empty cells.

Constraints

Limits and guarantees your solution can rely on.

1 <= N <= 100
1 <= M <= 100
0 <= ar[j] <= 2