598.Zombie in Matrix

1.Description(Medium)

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.

Example

Given a matrix:

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

return2

2.Code

这道题目跟611很相似，首先要手动加上坐标机制 class Coordinate

611中判断是不是边界和是否是障碍为函数inBound，不是就直接continue

598中判断是不是边界和是不是people为函数isPeople,不是就直接continue;

每次把僵尸放进队列，一开始先计数people的个数，每次变成一个僵尸就count--;如果变成了0就直接return当前days,如果没有，就把变成的这些僵尸放进队列进行下次循环。

class Coordinate{
    public int x,y;
    public Coordinate(int x,int y){
        this.x=x;
        this.y=y;
    }
}

public class Solution_598 {
    /**
     * @param grid  a 2D integer grid
     * @return an integer
     */
    public int m,n;
    public int people=0;
    public int zombie=1;
    public int wall=2;
    public int[] deltaX={1,0,-1,0};
    public int[] deltaY={0,1,0,-1};

    public int zombie(int[][] grid) {
        if(grid==null || grid.length==0 || grid[0].length==0){
            return -1;
        }
        m=grid.length;
        n=grid[0].length;

        int peoplecount=0;
        //queue store the zombie
        Queue<Coordinate> queue=new LinkedList<Coordinate>();

        //Initial the queue for zombie and count people
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==people){
                    peoplecount++;
                }
                else if(grid[i][j]==zombie){
                    queue.offer(new Coordinate(i,j));
                }
            }          
        }
        //corner case
        if(peoplecount==0){
            return 0;
        }

        int days=0;
        while(!queue.isEmpty()){
            //每次进入while循环就是一个新的level，所以要+1；
            //在一个while中for循环把所有的元素都poll出去了
            days++;
            int size=queue.size();
            for(int i=0;i<size;i++){
                Coordinate current=queue.poll();
                for(int direction=0;direction<4;direction++){
                    Coordinate neighbor=new Coordinate(
                            current.x+deltaX[direction],
                            current.y+deltaY[direction]);
                    if(!isPeople(neighbor,grid)){
                        continue;
                    }
                    grid[neighbor.x][neighbor.y]=zombie;
                    peoplecount--;
                    //每次把人变成僵尸后要将peoplecount-1,然后判断下如果已经把所有的人都变成僵尸了就直接return.
                    if(peoplecount==0){
                        return days;
                    }
                    //put the zombie into queue
                    queue.offer(neighbor);                   
                }
            }
        }
        return -1;       
    }

    public boolean isPeople(Coordinate coor,int[][] grid){
        if(coor.x<0 || coor.x>=m) { return false; }
        if(coor.y<0 || coor.y>=n) { return false; }
        return (grid[coor.x][coor.y]==people);        
    }
}