标题：计算疫情扩散时间 | 时间限制：1秒 | 内存限制：32768K | 语言限制：不限

在一个地图中(地图由n*n个区域组成），有部分区域被感染病菌。感染区域每天都会把周围（上下左右）的4个区域感染。

请根据给定的地图计算，多少天以后，全部区域都会被感染。

如果初始地图上所有区域全部都被感染，或者没有被感染区域，返回-1

#include<bits/stdc++.h>

using namespace std;

int InfectAll(vector<int>& nums)
{
    int n = nums.size(), sum = 0;
    int N = sqrt(n), k = 0;
    vector<vector<int>> dp(N,vector<int>(N));
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            dp[i][j] = nums[k];
            sum += nums[k];
            k++;
        }
    }
    if(sum==0||sum==n) return -1;
    int count = 0;
    while(sum<n)
    {
        vector<vector<int>> temp = dp;
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                if(dp[i][j]==0)
                {
                    if ((i-1>=0&&temp[i-1][j]==1)||(j-1>=0&&temp[i][j-1]==1)||(i+1<N&&temp[i+1][j]==1)||(j+1<N&&temp[i][j+1]==1))
                    {
                        dp[i][j]=1;
                        sum++;
                    }
                }
            }
        }
        count++;
    }
    return count;
}

int main(){
    string input;
    int target;
    getline(cin,input);
    
    vector<int> nums;
    int num = 0;
    for(int i=0;i<=input.size();i++)
    {
        if(input[i]==','||i==input.size())
        {
            nums.push_back(num);
            num = 0;
        }
        else num = num*10 + (input[i]-'0');
    }
    
    cout<<InfectAll(nums)<<endl;
    
    return 0;
}

计算疫情扩散时间

全站热榜