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):

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;
    }
}