FastPrep
Problem · Matrix

Virus Spread (Intuit India)

● MediumIntuitINTERNOA

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.

    Examples
    01 · Example 1
    N = 2
M = 3
grid = [[2, 0, 0], [1, 1, 1]]
return = 3
    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.
    02 · Example 2
    N = 2
M = 3
grid = [[2, 0, 1], [1, 1, 0]]
return = -1
    The healthy cell in the top right will not be infected since it is surrounded by empty cells.
    Constraints
    • 1 <= N <= 100
    • 1 <= M <= 100
    • 0 <= ar[j] <= 2
    More Intuit problems
    drafts saved locally
    public int minimumTimeToInfect(int N, int M, int[][] grid) {
    // write your code here
}
    N2
    M3
    grid[[2, 0, 0], [1, 1, 1]]
    expected3
    sign in to submit