LintCode - 598 Zombie in Matrix

https://xuezhashuati.blogspot.com/2017/03/lintcode-598-zombie-in-matrix.html
Given a 2D grid, each cell is either a wall 2, a zombie 1 or people 0 (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 -1 if can not turn all people into zombies.

Example
Given a matrix:

0 1 2 0 0
1 0 0 2 1
0 1 0 0 0
return 2

思路
找最少时间，又要用搜索，想到BFS。没什么特别的思路。
先过一遍矩阵，把zombie的位置都丢到queue里，并统计人的数量。
然后开始从这些zombie出发上下左右去把人变成zombile。变一个，人的数量要减1。
如果没有人了。说明搞完了。
如果循环出来人还没死光，说明搞不定了。返回-1。

    public int zombie(int[][] grid) {        
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return 0;
        }
        
        int people = 0;
        Queue<Point> queue = new LinkedList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    people++;
                }
                if (grid[i][j] == 1) {
                    queue.offer(new Point(i, j));
                }
            }
        }
        if (people == 0) {
            return 0;
        }
        
        int[] directionX = new int[] {-1, 1, 0, 0};
        int[] directionY = new int[] {0, 0, -1, 1};
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Point pt = queue.poll();
                for (int j = 0; j < 4; j++) {
                    Point next = new Point(pt.x + directionX[j], pt.y + directionY[j]);
                    if (isValid(grid, next) && grid[next.x][next.y] == 0) {
                        grid[next.x][next.y] = 1;
                        people--;
                        queue.offer(next);
                    }
                }
            }
            step++;
            if (people == 0) {
                return step;
            }
        }
        
        return -1;
        
    }
    
    public boolean isValid(int[][] grid, Point pt) {
        return pt.x >= 0 && pt.x < grid.length 
            && pt.y >= 0 && pt.y < grid[0].length 
            && grid[pt.x][pt.y] != 2;
    }

http://blog.hyoung.me/cn/2017/03/breadth-first-search-ii/

这道题虽然没有明确说要计算最短路径，但仔细分析题意，便可发现僵尸感染的过程便是 BFS 拓展的过程，然后将所有人都感染的天数则是最后一个人被感染所需要的最短天数。

在这里，为了快速判断所有人都被感染了，我们先统计所有存活的人，然后根据感染情况不断地去更新这个数字，当其为0时，所有的人就都被感染了。

http://www.jiuzhang.com/solutions/zombie-in-matrix/
－ Use enum

    public int PEOPLE = 0;
    public int ZOMBIE = 1;
    public int WALL = 2;
    
    public int[] deltaX = {1, 0, 0, -1};
    public int[] deltaY = {0, 1, -1, 0};
     
    /**
     * @param grid a 2D integer grid
     * @return an integer
     */
    public int zombie(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        
        int n = grid.length;
        int m = grid[0].length;
        
        // initialize the queue & count people
        int people = 0;
        Queue<Coordinate> queue = new LinkedList<>();
        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 Coordinate(i, j));
                }
            }
        }
        
        // corner case
        if (people == 0) {
            return 0;
        }
        
        // bfs
        int days = 0;
        while (!queue.isEmpty()) {
            days++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Coordinate zb = queue.poll();
                for (int direction = 0; direction < 4; direction++) {
                    Coordinate adj = new Coordinate(
                        zb.x + deltaX[direction],
                        zb.y + deltaY[direction]
                    );
                    
                    if (!isPeople(adj, grid)) {
                        continue;
                    }
                    
                    grid[adj.x][adj.y] = ZOMBIE;
                    people--;
                    if (people == 0) {
                        return days;
                    }
                    queue.offer(adj);
                }
            }
        }
        
        return -1;
    }
    
    private boolean isPeople(Coordinate coor, int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        
        if (coor.x < 0 || coor.x >= n) {
            return false;
        }
        if (coor.y < 0 || coor.y >= m) {
            return false;
        }
        return (grid[coor.x][coor.y] == PEOPLE);
    }