Given a 2D grid, each cell is either a wall2, a zombie1or people0(the number zero, one, two).Zombies can turn the nearest people(up/down/left/right) into zombies every day, but can not through wall. How long will it take to turn all people into zombies? Return-1if can not turn all people into zombies.

Have you met this question in a real interview?

Yes

Example

Given a matrix:

0 1 2 0 0
1 0 0 2 1
0 1 0 0 0

return2

1. we can conquer this in two steps
   1. get all the coordinate of the zombie position (will can in this step, count the number of people too)
   2. BFS in level order, how many level is how many days it will take to convert all zombie && if the people count is 0 that means all is converted, otherwise return -1

public class Solution {
    /**
     * @param grid  a 2D integer grid
     * @return an integer
     */
    public int ZOMBIE = 1;
    public int PEOPLE = 0;
    public int WALL = 2;

    public int[] deltaX = {1, -1, 0, 0};
    public int[] deltaY = {0, 0, 1, -1};

    class Pair {
        int n;
        int m;
        public Pair (int n, int m) {
            this.n = n;
            this.m = m;
        }
    }
    public int zombie(int[][] grid) {
        // Write your code here
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return -1;
        }

        int n = grid.length;
        int m = grid[0].length;

        //step 1 : get the position of the zombie into the queue
        Queue<Pair> queue = new LinkedList<>();

        //count the number of people in the matrix
        int people = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == PEOPLE) {
                    people++;
                } else if (grid[i][j] == ZOMBIE) {
                    queue.offer(new Pair(i, j));
                }
            }
        }

        //bfs for the number of days, the number of level is the number of days
        int days = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            days++;
            for (int i = 0; i < size; i++) {
                Pair cur = queue.poll();
                for (int j = 0; j < 4; j++) {
                    int neighborN = cur.n + deltaX[j];
                    int neighborM = cur.m + deltaY[j];

                    Pair neighbor = new Pair(neighborN, neighborM);
                    if (!checkBoundary(neighbor, grid)) {
                        continue;
                    }

                    people--;
                    if (people == 0) {
                        return days;
                    }
                    grid[neighborN][neighborM] = ZOMBIE;
                    queue.offer(neighbor);

                }
            }
        }

        return -1;


    }


    public boolean checkBoundary(Pair pair, int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;

        if (pair.n < 0 || pair.n >= n) {
            return false;
        }

        if (pair.m < 0 || pair.m >= m) {
            return false;
        }

        return grid[pair.n][pair.m] == PEOPLE;
    }
}