僵尸矩阵 · Zombie in Matrix（多原bfs）

给定一个 2D 网格每个单元格要么是墙 2要么是僵尸 1要么是人 0数字 0、1、2。僵尸每天可以将最近的人上/下/左/右变成僵尸但是 不能穿墙。 把所有人都变成僵尸需要多长时间 如果不能将所有人变成僵尸则返回 -1。题解九章算法 - 帮助更多程序员找到好工作硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧多源点bfs。 从所有的源点出发往外感染即可。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; QueueCoordinate 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); } }