31 僵尸矩阵（Zombie In Matrix）

文章目录

• • 1 题目
  • 2 解决方案
  • • 2.1 思路
    • 2.2 时间复杂度
    • 2.3 空间复杂度
  • 3 源码

1 题目

题目：僵尸矩阵（Zombie In Matrix）
描述：给一个二维网格，每一个格子都有一个值，2 代表墙，1 代表僵尸，0 代表人类(数字 0, 1, 2)。僵尸每天可以将上下左右最接近的人类感染成僵尸，但不能穿墙。将所有人类感染为僵尸需要多久，如果不能感染所有人则返回 -1。

lintcode题号——598，难度——medium

样例1：

输入:
[[0,1,2,0,0],
 [1,0,0,2,1],
 [0,1,0,0,0]]
输出:2

样例2：

输入:
[[0,0,0],
 [0,0,0],
 [0,0,1]]
输出:4

2 解决方案 2.1 思路

  通过对二维数组的遍历找到并记录僵尸位置和人类的数量，然后以僵尸的位置为起点（多个起点）用宽度优先搜索找到相邻的人类（忽略找到的僵尸和墙）咬一口感染，并将人类数量减1，直到人类数量为0为止，宽搜过程中需要按层搜索，每层即是一天的时间。

2.2 时间复杂度

  图上的宽度优先搜索，算法的时间复杂度为O(n+m)，其中n为节点数，m为边数。R行C列的矩阵，可以看成有R*C个节点和R*C*2条边的图，在其上进行BFS，时间复杂度为O(R*C)。

2.3 空间复杂度

  图上的宽度优先搜索，使用了queue队列数据结构，队列最大容量为节点数，即R*C，算法的空间复杂度为O(R*C)。

3 源码

细节：

1. 使用宽度优先搜索找到相邻的人类进行感染。
2. 记录原始僵尸的位置，计算初始人类数量用于之后判断是否已经全部感染。
3. 由于要记录天数，所以需要进行层级遍历，进入循环时记录queue的大小，每次循环完一轮表示一天。

C++版本：

/**
* @param grid: a 2D integer grid
* @return: an integer
*/
int zombie(vector> &grid) {
    // write your code here
    int result = 0;
    if (grid.empty() && grid.front().empty())
    {
        return 0;
    }

    // 记录僵尸位置和人类的数量
    vector> zombiePos;
    int humanCount = 0;
    for (int i = 0; i < grid.size(); i++)
    {
        for (int j = 0; j < grid.front().size(); j++)
        {
            if (grid.at(i).at(j) == 1)
            {
                zombiePos.push_back({i, j});
            }
            else if (grid.at(i).at(j) == 0)
            {
                humanCount++;
            }
        }
    }

    queue> posQueue;
    for (auto it : zombiePos) // 起点为多个原始僵尸的位置
    {
        posQueue.push(it);
    }
    int a[4] = {0, 0, 1, -1};
    int b[4] = {1, -1, 0, 0};
    while (!posQueue.empty())
    {
        int size = posQueue.size(); // 记录该层的僵尸数
        for (int i = 0; i < size; i++) // 遍历该层所有僵尸，进行宽搜
        {
            int x = posQueue.front().first;
            int y = posQueue.front().second;
            posQueue.pop();
            for (int j = 0; j < 4; j++) // 向四个方向寻找人类咬一口
            {
                int neighbourX = x + a[j];
                int neighbourY = y + b[j];
                if (isValid(grid, neighbourX, neighbourY) == true
                && grid.at(neighbourX).at(neighbourY) == 0) // 如果该位置是人类，则感染
                {
                    grid.at(neighbourX).at(neighbourY) = 1;
                    posQueue.push({neighbourX, neighbourY});
                    humanCount--; // 感染后，人类数量减1
                }
            }
        }

        result++; // 每扩展一层，天数加1
        
        if (humanCount == 0) // 没有人类的时候，则返回结果天数
        {
            return result;
        }
    }

    return -1;
}

// 判断坐标是否越界
bool isValid(vector> & grid, int x, int y)
{
    int maxRow = grid.size() - 1;
    int maxCol = grid.front().size() - 1;
    if (x < 0 || x > maxRow)
    {
        return false;
    }
    if (y < 0 || y > maxCol)
    {
        return false;
    }

    return true;
}