Zombie in Matrix

Solution:

public class Solution {
    /*
     * @param grid: a 2D integer grid
     * @return: an integer
     */
    public int zombie(int[][] grid) {
        // write your code here
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return -1;
        int m = grid.length;
        int n = grid[0].length;
        int pplCount = 0;
        int res = 0;
        int[] dx = new int[]{0, 0, 1, -1};
        int[] dy = new int[]{1, -1, 0, 0};
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int  j = 0; j < n; j++) {
                if (grid[i][j] == 0) pplCount++;
                if (grid[i][j] == 1) queue.add(i*n + j);
            }
        }
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            res++;
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                for (int q = 0; q < 4; q++) {
                            int newx = cur / n + dx[q];
                            int newy = cur % n + dy[q];
                            if (newx < 0 || newx >= m || newy < 0 || newy >= n || grid[newx][newy] == 1|| grid[newx][newy] == 2 ) {
                                continue;
                            }
                            queue.add(newx * n + newy);
                            grid[newx][newy] = 1;
                            pplCount--;
                            if (pplCount == 0) return res;
                }
            }
        }
        
        return -1;
    }
}

---------------------------------------------------------------------------------------------------------
思路：

这题的关键点是如何计算days. 因为zombie每天只能上下左右各走一步，相当于BFS往下走一层。所以在BFS的时候需要分层来做。每走一层就是一天。

实现：
需要创建一个Coordinate类来保存坐标。在更新days的时候，应该放在while循环开头。如果在结尾，当前循环恰好满足吃掉所有人，就返回了，那么当前那一天就没有记录。

在分层遍历的时候，queue.size()需要一个变量保存。因为queue是reference type，BFS时size是变化的。