598 · Zombie in Matrix [LintCode]

一刷 05/2022

 Version #1 BFS

Time O(MN)

Spance O(MN)

361 mstime cost

·

22.63 MBmemory cost

·

Your submission beats16.20 %Submissions

public class Solution {

/**

* @param grid: a 2D integer grid

* @return: an integer

*/

private static int WALL = 2;

private static int ZOMBIE = 1;

private static int HUMAN = 0;

private int[] dx = new int[]{1, 0, -1, 0};

private int[] dy = new int[]{0, -1, 0, 1};

public int zombie(int[][] grid) {

if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {

return 0;

}

int rows = grid.length, cols = grid[0].length;

Queue<int[]> que = new ArrayDeque<>();

boolean[][] visited = new boolean[rows][cols];

int humanCnt = 0;

for (int y = 0; y < rows; y++) {

for (int x = 0; x < cols; x++) {

if (grid[y][x] == HUMAN) {

humanCnt++;

}

if (grid[y][x] == ZOMBIE) {

visited[y][x] = true;

que.offer(new int[]{x, y});

}

}

}

int days = 0;

while (!que.isEmpty()) {

int size = que.size();

days++;

while (size-- > 0) {

int[] curr = que.poll();

for (int i = 0; i < 4; i++) {

int nx = curr[0] + dx[i];

int ny = curr[1] + dy[i];

if (nx < 0 || nx >= cols || ny < 0 || ny >= rows) {

continue;

}

if (visited[ny][nx] || grid[ny][nx] == WALL) {

continue;

}

if (grid[ny][nx] == HUMAN) {

humanCnt--;

}

visited[ny][nx] = true;

que.offer(new int[]{nx, ny});

}

}

if (humanCnt == 0) {

return days;

}

}

return -1;

}