【题目描述】
给一个二维网格,每一个格子都有一个值,2 代表墙,1 代表僵尸,0 代表人类(数字 0, 1, 2)。僵尸每天可以将上下左右最接近的人类感染成僵尸,但不能穿墙。将所有人类感染为僵尸需要多久,如果不能感染所有人则返回 -1。
【题目样例】
例1:
输入:
[[0,1,2,0,0],
[1,0,0,2,1],
[0,1,0,0,0]]
输出:
2
例2:
输入:
[[0,0,0],
[0,0,0],
[0,0,1]]
输出:
4
【评测与题解】
→戳这里在线评测及查看题解
/**
* 本参考程序来自九章算法,由 @九章算法 提供。版权所有,转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作,教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括:九章算法班,系统设计班,算法强化班,Java入门与基础算法班,Android 项目实战班,
* - Big Data 项目实战班,算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站:http://www.jiuzhang.com/?source=code
*/
class Coordinate {
int x, y;
public Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Solution {
public int PEOPLE = 0;
public int ZOMBIE = 1;
public int WALL = 2;
public int[] deltaX = {1, 0, 0, -1};
public int[] deltaY = {0, 1, -1, 0};
/**
* @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;
}
int n = grid.length;
int m = grid[0].length;
// initialize the queue & count people
int people = 0;
Queue<Coordinate> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == PEOPLE) {
people++;
} else if (grid[i][j] == ZOMBIE) {
queue.offer(new Coordinate(i, j));
}
}
}
// corner case
if (people == 0) {
return 0;
}
// bfs
int days = 0;
while (!queue.isEmpty()) {
days++;
int size = queue.size();
for (int i = 0; i < size; i++) {
Coordinate zb = queue.poll();
for (int direction = 0; direction < 4; direction++) {
Coordinate adj = new Coordinate(
zb.x + deltaX[direction],
zb.y + deltaY[direction]
);
if (!isPeople(adj, grid)) {
continue;
}
grid[adj.x][adj.y] = ZOMBIE;
people--;
if (people == 0) {
return days;
}
queue.offer(adj);
}
}
}
return -1;
}
private boolean isPeople(Coordinate coor, int[][] grid) {
int n = grid.length;
int m = grid[0].length;
if (coor.x < 0 || coor.x >= n) {
return false;
}
if (coor.y < 0 || coor.y >= m) {
return false;
}
return (grid[coor.x][coor.y] == PEOPLE);
}
}
//version 硅谷算法班
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 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 = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};
int dist = 0;
while (!qx.isEmpty()) {
dist++;
int size = qx.size();
for (int i = 0; i < size; i++) {
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 && 0 <= ny && 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;
}
}
网友评论