31 僵尸矩阵(Zombie In Matrix)

31 僵尸矩阵(Zombie In Matrix),第1张

文章目录
    • 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;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/737550.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-28
下一篇 2022-04-28

发表评论

登录后才能评论

评论列表(0条)

保存