LintCode 598 Zombie in Matrix

思路

棋盘图bfs。
用bfs从zombie开始向人类进行感染（搜索），这里需要一层一层地搜索：bfs中每次将下一层的所有元素都放到队列里（类似二叉树zigzag层序遍历那题），同时将下一层元素从0标记为1，记录层数depth。开始的时候需要记录下人类数量，最后检查人类的数量是否为0，如果不为0说明有的人类无法被感染，返回-1；否则，需要返回depth-1，因为最后无法继续向四周扩展的时候，循环外还是进行了depth++。

代码

public class Solution {
    /*** @param grid: a 2D integer grid* @return: an integer*/public int zombie(int[][] grid) {
    // write your code hereif(grid == null || grid.length == 0 || grid[0].length == 0)return 0;int row = grid.length;int col = grid[0].length;int[] dx = {
    0, 0, 1, -1};int[] dy = {
    1, -1, 0, 0};Queue<Integer> qx = new LinkedList<>();Queue<Integer> qy = new LinkedList<>();int zomCount = 0;for(int i = 0; i < row; i++) {
    for(int j = 0; j < col; j++) {
    if(grid[i][j] == 1) {
    qx.offer(i);qy.offer(j);} else if(grid[i][j] == 0) {
    zomCount++;}}}int depth = 0;while(!qx.isEmpty()) {
    int size = qx.size();for(int i = 0; i < size; i++) {
    int cx = qx.poll(), cy = qy.poll();for(int j = 0; j < 4; j++) {
    int nx = cx + dx[j];int ny = cy + dy[j];if(0 <= nx && nx < row && 0 <= ny && ny < col && grid[nx][ny] == 0) {
    grid[nx][ny] = 1;qx.offer(nx);qy.offer(ny);zomCount--;}}}depth++;}if(zomCount > 0) return -1;return depth - 1;}
}

复杂度

时间复杂度O($n?m$)，因为每个元素最多被访问1次
空间复杂度O($n?m$)