计算疫情扩散时间
标题：计算疫情扩散时间 | 时间限制：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;
}
平安产险科技中心工作强度 24人发布
