3022: 流感传染 (循环和bfs)

解题思路:
两种方法，也是两种思路，第一种，每一天遍历地图一遍，如果当前格子没有被感染，就看它上下左右是否有感染源，今天是否会被感染，被感染则标记@。

第二种方法，使用队列进行bfs搜索，将每一天的感染源加入队列，向上下左右进行感染扩散，直到没有病人被感染和到达规定天数。

一个是看健康的人是否会被感染，一个是感染源进行扩散。

注意：问题是输入第m天被感染的人数，所以只感染了m-1天。

第一种方法代码：

#include <bits/stdc++.h>

using namespace std;

int dx[4]= {-1,1,0,0}; //上 下 左 右
int dy[4]= {0,0,-1,1};

char dp[107][107],sp[107][107];//sp数组用来存放当天感染前的情况

int main () {
	int n,m,z=0;
	cin>>n;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			cin>>dp[i][j];
			sp[i][j]=dp[i][j];
		}
	}
	cin>>m;
	m--;//注意，只感染了m-1天，所以要进行-1
	while(m--) {

		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {//遍历地图
				
				if(sp[i][j]=='.') {//如果是健康的人

					for(int k=0; k<4; k++) {//四个方向进行搜索
						int x=i+dx[k],y=j+dy[k];
						if(x>0&&x<=n&&y>0&&y<=n) {//如果没有超出地图
							if(sp[x][y]=='@') {//注意这里是sp数组，当天感染前周围有病人
								dp[i][j]='@';//则被感染
								break;
							}
						}
					}
				}

			}
		}
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				sp[i][j]=dp[i][j];//将这一天的感染情况赋值给sp数组
//				cout<<dp[i][j]<<" \n"[j==n];//打印看每一天的感染情况
			}
		}

	}

	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			if(dp[i][j]=='@')z++;//计算感染人数
		}
	}
	cout<<z;


	return 0;
}

这里有一个细节，需要记录下当天开始感染前的地图，不然遍历到后面的时候搜索到的感染源是今天新增的，也会被感染。

第二种方法：

#include <bits/stdc++.h>

using namespace std;

struct node {
	int x,y,l;//l表示天数
};
queue<node>q;

int dx[4] = {-1,1,0,0}; //上 下 左 右
int dy[4] = {0,0,-1,1};

char dp[107][107];
int  z = 0;//记录被感染的人数

void bfs(int n,int m) {

	while(!q.empty()) {//如果队列不为空
		node now = q.front();//取出队首的感染源
		q.pop();//队首出列

		if(now.l>=m)break;//如果天数大于等于m，即为结束，因为是第m天，所以有等号

		for(int i=0; i<4; i++) {//四个方向搜索
			int x=now.x+dx[i],y=now.y+dy[i];
			if(x>0&&x<=n&&y>0&&y<=n) {//不超过地图
				if(dp[x][y]=='.') {//周围是健康的人
					dp[x][y]='@';
					z++;//感染人数+1
					node n;//将这个人也记为感染源
					n.x = x;
					n.y = y;
					n.l = now.l+1;//注意天数+1
					q.push(n);//加入到队列中
				}
			}
		}

	}

}

int main () {
	int n,m;
	cin>>n;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			cin>>dp[i][j];
			if(dp[i][j]=='@') {
				z++;
				node n;//地图中初始的感染源加入到队列中
				n.x = i;
				n.y = j;
				n.l = 1;//为第一天
				q.push(n);
			}
		}
	}
	cin>>m;

	bfs(n,m);

	cout<<z;


	return 0;
}

相比之下还是bfs比较简单，需要思考的也少。

以上。