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 it takes to infect all humans?

Input

matrix: a 2D integer array where a[i][j] = 1 represents a zombie in the cell and a[i][j] = 0 represents a human in 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