Zombie in Matrix

• Lintcode : 598 / Leetcode :
• Level : Medium

Problem

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

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(m n)
space: O(m n) 最壞

Answer

class Solution {
public:
    int zombie(vector<vector<int>> &grid) {
        if (grid.size() == 0 || grid[0].size() == 0) return 0;
        queue<vector<int>> q;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) q.push({i, j});
            }
        }
        int days = -1;
        while (!q.empty()) {
            int s = q.size();
            days += 1;
            for (int i = 0; i < s; i++) {
                vector<int> axis = q.front(); q.pop();
                for (auto d : dir) {
                    int x = d[0] + axis[0];
                    int y = d[1] + axis[1];
                    if (!isValid(grid, x, y)) continue;
                    q.push({x, y});
                    grid[x][y] = 1;
                }
            }
        }
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 0) return -1;
            }
        }
        return days;
    }
    vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    bool isValid (vector<vector<int>> &grid, int x, int y) {
        if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] != 0)
            return false;
        return true;
    }
};

tags: BFS

​