Lintcode 598. Zombie in Matrix

Given a 2D grid, each cell is either a wall 2, a zombie 1 or people 0 (the number zero, one, two).Zombies can turn the nearest people(up/down/left/right) into zombies every day, but can not through wall. How long will it take to turn all people into zombies? Return -1 if can not turn all people into zombies.

Example

Example 1:

Input:
[[0,1,2,0,0],
 [1,0,0,2,1],
 [0,1,0,0,0]]
Output:
2

Example 2:

Input:
[[0,0,0],
 [0,0,0],
 [0,0,1]]
Output:
4

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

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) {             return 0;         }           int ans = 0;         int nRows = grid.length;         int nCols = grid[0].length;         int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};           Queue<Integer> queue = new LinkedList<>();         boolean[][] visited = new boolean[nRows][nCols];           // step 1: put all 1s to the queue         //         for (int i = 0; i < nRows; i++) {             for (int j = 0; j < nCols; j++) {                 if (grid[i][j] == 1) {                     queue.offer(i * nCols + j);                     visited[i][j] = true;                 }             }         }           while (!queue.isEmpty()) {             int size = queue.size();             ans += 1;             for (int i = 0; i < size; i++) {                 int curNode = queue.poll();                 for (int j = 0; j < 4; j++) {                     int nx = curNode / nCols + dirs[j][0];                     int ny = curNode % nCols + dirs[j][1];                       if (isValid(grid, visited, nx, ny)) {                         queue.offer(nx * nCols + ny);                         visited[nx][ny] = true;                         grid[nx][ny] = 1; // mark as zoobie                     }                 }             }         }           // finally check if there are still zero 0s         //         for (int i = 0; i < nRows; i++) {             for (int j = 0; j < nCols; j++) {                 if (grid[i][j] == 0) {                     return -1;                 }             }         }           return ans;     }       private boolean isValid(int[][] grid, boolean[][] visited, int x, int y) {         int nRows = grid.length;         int nCols = grid[0].length;           return x >= 0 && x < nRows && y >= 0 && y < nCols && !visited[x][y] && grid[x][y] == 0;     } }