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:

1var matrix = [
2  [0, 1, 1, 0, 1],
3  [0, 1, 0, 1, 0],
4  [0, 0, 0, 0, 1],
5  [0, 1, 0, 0, 0]
6]

Output: 2

Explanation:

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

1var matrix = [
2  [1, 1, 1, 1, 1],
3  [1, 1, 1, 1, 1],
4  [0, 1, 0, 1, 1],
5  [1, 1, 1, 0, 1]
6]

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

1var matrix = [
2  [1, 1, 1, 1, 1],
3  [1, 1, 1, 1, 1],
4  [1, 1, 1, 1, 1],
5  [1, 1, 1, 1, 1]
6]

Try it yourself