[LintCode] 598 Zombie in Matrix 解题报告

Description
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。


Code

public class Solution {
    /**
     * @param grid  a 2D integer grid
     * @return an integer
     */
     
    class Point{
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    } 
    public int zombie(int[][] grid) {
        // Write your code here
        
        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;
    }
}