欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

新冠病毒的传播(bfs)

程序员文章站 2024-03-08 10:58:28
...

题目描述
最近新冠病毒疫情非常严重,由于我们国家采取了有力的措施,才没有使疫情进一步的扩大。今天,作为计算机专业的学生,我们来用程序模拟一下各种情况下的新冠病毒传播情况。现在给定一个n * m的网格,每个网格可以有以下三个值之一:

值 0 代表隔离带。

值 1 代表健康人群。

值 2 代表感染人群。

每天,任何与感染人群(在 4 个正方向上)相邻的健康人都会感染。如果遇到隔离带,病毒就会被阻断。
输出直到单元格中没有健康人为止所必须经过的最小天数。如果不可能所有人都被感染,输出 -1。
输入
测试数据由多组测试样例组成。第一行输入两个正整数 n ( 1 <= n <= 500 ) 和 m ( 1 <= m <= 500 ),

接下来输入n * m个数字,数字均由 0 , 1 ,2构成
输出
每组测试样例,输出直到单元格中没有健康人为止所必须经过的最小天数。如果不可能,输出 -1。
新冠病毒的传播(bfs)
还是觉得bfs挺麻烦的,这题先把最初的感染者放入数组里,然后四个方向判断,有就感染放入数组,知道没有可以咬的为止,OK Its My Time。

#include<bits/stdc++.h>
using namespace std;
int a[505][505];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m;
struct node{
 int x,y,cnt;
};
bool dio(){
 for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++)
      if(a[i][j]==1)return 1;
  }
 return 0; 
}
int bfs(){
 queue<node>q;
 node nex,xia;
 int Max=0;
 for(int i=1;i<=n;i++){
  for(int j=1;j<=m;j++){
   if(a[i][j]<2)continue;
   nex.x=i,nex.y=j,nex.cnt=0;
   q.push(nex);
  }
 }
 while(!q.empty()){
  nex=q.front();
  q.pop();
  for(int i=0;i<4;i++){
   if(a[nex.x+dir[i][0]][nex.y+dir[i][1]]==1){
    xia.x=nex.x+dir[i][0];
    xia.y=nex.y+dir[i][1];
    xia.cnt=nex.cnt+1;
    a[xia.x][xia.y]=2;
    q.push(xia);
    Max=max(Max,xia.cnt);
   }
  }
 }
 return Max;
}
int main(){
 ios::sync_with_stdio(false);
 while(cin>>n>>m){
  for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++)
    cin>>a[i][j];
   }
   if(dio()==0)cout<<0<<endl;
  else {
   int Max=bfs();
   if(dio())cout<<-1<<endl;
   else cout<<Max<<endl;
  }
 }
 return 0;
} 
相关标签: 算法