计算疫情扩散时间

一.题目

二.歧义

此题没有歧义

三.解题思路

这道题剔除一些无关简要的代码，就是一个循环就搞定了。

四.代码

1.主函数

先上主流程

因为题目中说了，输入的数据是以“，”分隔，所以上来就是分割
对生产出来的数据进行校验
根据用户输入的数据初始化地图信息
校验是否全部感染或者全部没有被感染
计算感染时间

void main()
{
    std::string str;
    std::string reg = ",";
    std::getline(std::cin, str);
    std::vector<int> nums = SplitStringToDigit(str, reg);

    if (nums.empty())
    {
        std::cout << "-1" << std::endl;
        return;
    }
    int n = std::sqrt(nums.size());
    //根据用户输入的数据 初始化地图信息
    InitMap(nums, n);
    //校验是否全部感染 或者 全部没有被感染
    if (IsAllInfect(n) || IsAllNoInfect(n))
    {
        std::cout << "-1" << std::endl;
        return;
    }
    std::cout << CalcInfectDays(n) << std::endl;

}

2.分割

因为题目中说了，输入的数据是以“，”分隔，所以必然还是老代码

//分隔字符串并将其转换为数字
std::vector<int> SplitStringToDigit(std::string& str, const std::string& reg)
{
    std::vector<int> result;
    std::string::size_type posLast = 0;
    std::string::size_type posCurrent = str.find(reg);

    while (posCurrent != std::string::npos)
    {
        result.push_back(str.substr(posLast, posCurrent - posLast).c_str()[0] - '0');
        posLast = posCurrent + reg.size();
        posCurrent = str.find(reg, posLast);
    }

    if (posLast < str.length())
    {
        result.push_back(str.substr(posLast).c_str()[0] - '0');
    }
    return result;
}

3.初始化地图

//根据输入的数据初始化map
void InitMap(const std::vector<int>& nums,int n)
{
    for (int i = 0; i < nums.size(); i++)
    {
        int row = i / n;
        int cell = i % n;
        map[row][cell] = nums[i];
    }
}

4.核心代码

//获取所有被感染的节点
std::vector<std::pair<int, int>> GetInfectNodes(int n)
{
    //获取所有被感染的节点
    std::vector<std::pair<int, int>> infectNodes;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            //0 没有被感染， 1被感染
            if (map[i][j] == 1)
            {
                infectNodes.push_back(std::make_pair(i, j));
            }
        }
    }
    return infectNodes;
}

int CalcInfectDays(int n)
{
    std::vector<std::pair<int, int>> infectNodes = GetInfectNodes(n);
    int days = 0;
    while (!IsAllInfect(n))
    {
        //病毒可以一传百，百传千，这里一定要重新获取病毒源
        infectNodes = GetInfectNodes(n);
        for (auto& node : infectNodes)
        {
            for (auto& dir : directions)
            {
                int row = node.first + dir[0];
                int cell = node.second + dir[1];
                //如果超越n的边界了，就不处理
                if (row < 0 || row >= n || cell < 0 || cell >= n) 
                    continue;
                map[row][cell] = 1;
            }
        }
        days++;
    }
    return days;
}

五.全部代码

#include <iostream>
#include <vector>
#include <cmath>
#include <string>


//分隔字符串并将其转换为数字
std::vector<int> SplitStringToDigit(std::string& str, const std::string& reg)
{
    std::vector<int> result;
    std::string::size_type posLast = 0;
    std::string::size_type posCurrent = str.find(reg);

    while (posCurrent != std::string::npos)
    {
        result.push_back(str.substr(posLast, posCurrent - posLast).c_str()[0] - '0');
        posLast = posCurrent + reg.size();
        posCurrent = str.find(reg, posLast);
    }

    if (posLast < str.length())
    {
        result.push_back(str.substr(posLast).c_str()[0] - '0');
    }
    return result;
}



//由于题目限定了地图的最大范围，这里设定一个最大二维数组
int map[200][200];
int directions[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };

//根据输入的数据初始化map
void InitMap(const std::vector<int>& nums,int n)
{
    for (int i = 0; i < nums.size(); i++)
    {
        int row = i / n;
        int cell = i % n;
        map[row][cell] = nums[i];
    }
}

//校验地图是否全部被感染了
bool IsAllInfect(int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            //0 没有被感染， 1被感染
            if (map[i][j] == 0) return false;
        }
    }
    return true;
}

//校验地图是否全部没有被感染
bool IsAllNoInfect(int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            //0 没有被感染， 1被感染
            if (map[i][j] == 1) return false;
        }
    }
    return true;
}

//获取所有被感染的节点
std::vector<std::pair<int, int>> GetInfectNodes(int n)
{
    //获取所有被感染的节点
    std::vector<std::pair<int, int>> infectNodes;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            //0 没有被感染， 1被感染
            if (map[i][j] == 1)
            {
                infectNodes.push_back(std::make_pair(i, j));
            }
        }
    }
    return infectNodes;
}

int CalcInfectDays(int n)
{
    std::vector<std::pair<int, int>> infectNodes = GetInfectNodes(n);
    int days = 0;
    while (!IsAllInfect(n))
    {
        //病毒可以一传百，百传千，这里一定要重新获取病毒源
        infectNodes = GetInfectNodes(n);
        for (auto& node : infectNodes)
        {
            for (auto& dir : directions)
            {
                int row = node.first + dir[0];
                int cell = node.second + dir[1];
                //如果超越n的边界了，就不处理
                if (row < 0 || row >= n || cell < 0 || cell >= n) 
                    continue;
                map[row][cell] = 1;
            }
        }
        days++;
    }
    return days;
}





void DebugTest()
{
    std::vector<int> nums = { 1,0,1,0,0,0,1,0,1 };
    int n = std::sqrt(nums.size());
    InitMap(nums, n);
    if (IsAllInfect(n) || IsAllNoInfect(n))
    {
        std::cout << "-1" << std::endl;
        return;
    }
    std::cout << CalcInfectDays(n) << std::endl;
}



void main()
{
    std::string str;
    std::string reg = ",";
    std::getline(std::cin, str);
    std::vector<int> nums = SplitStringToDigit(str, reg);

    if (nums.empty())
    {
        std::cout << "-1" << std::endl;
        return;
    }
    int n = std::sqrt(nums.size());
    //根据用户输入的数据 初始化地图信息
    InitMap(nums, n);
    //校验是否全部感染 或者 全部没有被感染
    if (IsAllInfect(n) || IsAllNoInfect(n))
    {
        std::cout << "-1" << std::endl;
        return;
    }
    std::cout << CalcInfectDays(n) << std::endl;

}

华为OD2024 E 文章被收录于专栏

实时更新华为2024 E卷答案