Zombie in Matrix

update Jul 18, 2017 23:00

lintcode

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

Given a matrix:

0 1 2 0 0
1 0 0 2 1
0 1 0 0 0
return 2

Basic Idea:

对每个僵尸做bfs，每次把周围的人变成僵尸，把新僵尸放入queue，同时跟踪遍历层数。 因为最后一次可能queue中仍有僵尸，但所有人已经僵尸化，所以我们可以每次bfs的时候记录是否有人被变成僵尸，如有，则ret += 1.

python code：

    class Solution:
        # @param {int[][]} grid  a 2D integer grid
        # @return {int} an integer

        # 对每个僵尸做bfs，每次把周围的人变成僵尸，把新僵尸放入queue，同时跟踪遍历层数。
        def zombie(self, grid):
            if not grid:
                return -1
            R = len(grid)
            C = len(grid[0])
            queue = collections.deque()
            for i in range(R):
                for j in range(C):
                    if grid[i][j] == 1:
                        queue.appendleft((i,j))
            ret = 0
            rdir = (-1, 0, 1, 0)
            cdir = (0, -1, 0, 1)
            while queue:
                size = len(queue)
                changed = False
                for i in range(size):
                    r, c = queue.pop()
                    for j in range(4):
                        m = r + rdir[j]
                        n = c + cdir[j]
                        if m < 0 or m >= R or n < 0 or n >= C: 
                            continue
                        if grid[m][n] == 0:
                            changed = True
                            grid[m][n] = 1
                            queue.appendleft((m, n))
                if changed:
                    ret += 1
            for i in range(R):
                for j in range(C):
                    if grid[i][j] == 0:
                        return -1
            return ret

Java Code:

    public class Solution {
        /**
         * @param grid  a 2D integer grid
         * @return an integer
         */
        public int zombie(int[][] grid) {
            if (grid == null || grid.length == 0) return -1;
            int R = grid.length;
            int C = grid[0].length;
            Deque<int[]> queue = new LinkedList<>();
            for (int i = 0; i < R; ++i) {
                for (int j = 0; j < C; ++j) {
                    if (grid[i][j] == 1) queue.addFirst(new int[]{i, j});
                }
            }
            int[] rdir = new int[]{-1, 0, 1, 0};
            int[] cdir = new int[]{0, -1, 0, 1};
            int ret = 0;
            while (! queue.isEmpty()) {
                int size = queue.size();
                boolean changed = false;
                for (int i = 0; i < size; ++i) {
                    int[] cord = queue.removeLast();
                    int r = cord[0];
                    int c = cord[1];
                    for (int j = 0; j < 4; ++j) {
                        int m = r + rdir[j];
                        int n = c + cdir[j];
                        if (m < 0 || m >= R || n < 0 || n >= C) continue;
                        if (grid[m][n] == 0) {
                            grid[m][n] = 1;
                            changed = true;
                            queue.addFirst(new int[]{m, n});
                        }
                    }
                }
                if (changed) ret++;
            }
            for (int i = 0; i < R; ++i) {
                for (int j = 0; j < C; ++j) {
                    if (grid[i][j] == 0) return -1;
                }
            }
            return ret;
        }
    }