Amazon Online Assessment (OA) - Zombie Matrix

Given a 2D grid, each cell is either a zombie or a human. Zombies can turn adjacent (up/down/left/right) human beings into zombies every day.

Find out how many days does it take to infect all humans?

Input

matrix: a 2D integer array where a[i][j] = 1 represents a zombie on the cell and a[i][j] = 0 represents a human on the cell.

Examples

Example 1:

Input:
var matrix = [
  [0, 1, 1, 0, 1],
  [0, 1, 0, 1, 0],
  [0, 0, 0, 0, 1],
  [0, 1, 0, 0, 0]
]
Output: 2
Explanation:

At the end of day 1, the status of the grid:

var matrix = [
  [1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1],
  [0, 1, 0, 1, 1],
  [1, 1, 1, 0, 1]
]

At the end of day 2, the status of the grid:

var matrix = [
  [1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1]
]

Try it yourself