Zombie in Matrix

Java

public class Solution {
    /**
     * @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;
			}
		
			Queue<Integer> qx = new LinkedList<>();
			Queue<Integer> qy = new LinkedList<>();
			boolean[][] v = new boolean[grid.length][grid[0].length];
			
			for (int i = 0; i < grid.length; i++) {
				for (int j = 0; j < grid[0].length; j++) {
					if (grid[i][j] == 1) {
						qx.offer(i);
						qy.offer(j);
						v[i][j] = true;
					}
				}
			}
			
			int[] dx = {0, 0, 1, -1};
			int[] dy = {1, -1, 0, 0};
		
			int dist = 0;
			while (!qx.isEmpty()) {
				dist++;            //有元素在队列中，但不表示这一层中僵尸有食物 little sucker
				int size = qx.size();
				for (int i = 0; i < size; i++) {  //在dist++ 之后进行尝试
					int cx = qx.poll();
					int cy = qy.poll();
					for (int k = 0; k < 4; k++) {
						int nx = cx + dx[k];
						int ny = cy + dy[k];
							if (0 <= nx && nx < grid.length && ny >= 0 && ny < grid[0].length && grid[nx][ny] == 0 && !v[nx][ny]) {  //只看人 -- 只看有没走过
								qx.offer(nx);   //骑士问题可以在这里马上返回
								qy.offer(ny);
								v[nx][ny] = true;
							}
					}
				}
			}
			dist--;
			for (int i = 0; i < grid.length; i++) {
				for (int j = 0; j < grid[0].length; j++) {
					if (grid[i][j] == 0 && !v[i][j]) {
						return -1; //没被感染过
					}
				}
			}
			return dist;
		}
}