Given a 2D grid, each cell is either a wall2, a zombie1or people0(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-1if can not turn all people into zombies.

Have you met this question in a real interview?

Yes

Example

Given a matrix:

0 1 2 0 0
1 0 0 2 1
0 1 0 0 0

return2

class Solution {
public:
    /**
     * @param grid  a 2D integer grid
     * @return an integer
     */
    int zombie(vector<vector<int>>& grid) {
        // Write your code here
        if (grid.empty() || grid[0].empty())
            return 0;
        int n = grid.size(), m = grid[0].size();
        queue<Position> q;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1)
                    q.push(Position(i, j));
            }
        }
        vector<vector<int>> offsets = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int step = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                Position p = q.front(); q.pop();
                for (auto& offset : offsets) {
                    int x = p.x + offset[0];
                    int y = p.y + offset[1];
                    if (x >= 0 && x < n && 
                        y >= 0 && y < m &&
                        grid[x][y] == 0) {
                            q.push(Position(x, y));
                            grid[x][y] = 1;
                        }
                }
            }
            ++step;
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 0) {
                    return -1;
                }

            }
        }

        return step - 1;
    }

    struct Position {
        int x, y;
        Position(int _x, int _y) : x(_x), y(_y){};
    };
};