病毒扩散

旧城等待， 2022-12-24 05:54 132阅读 0赞

## 病毒扩散 ##

Description  
2019-ncov的突然出现扰乱了人们的日常生活，它具有极强的传染性，可以快速的在人群中扩散，现在研究人员正在模拟其在人群中的扩散情况.

在一个n\*m矩阵所示的人群中，\*为普通人，\#为佩戴口罩的人，@为病毒携带者，已知每秒每位病毒携带者会将病毒传染给相邻八个方向的未戴口罩的普通人。请问 x 秒后会有多少名传染者（初始为第0秒）？

Input  
第一行输入空格分隔的三个数n，m，x代表n行，m列的空间，x秒（n,m<=1000)。

接下来n行每行m人如上述所示。

Output  
一个数字，代表最终被传染的人数。

Sample  
Input  
![在这里插入图片描述][20201127005030767.png_pic_center]  
Output  
12

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    struct node
    {
        
    	int x, y;
    }ans[1000000];//注意数组大小
    int map[1000][1000], vis[1100][1100];
    int in,out,n,m;
    //dx，dy八个方向
    int dx[] = {
        1,1,0,-1,-1,-1,0,1};
    int dy[] = {
        0,1,1,1,0,-1,-1,-1};
    void BFS(int x, int y)
    {
        
    	for (int i = 0; i < 8; i++)//寻找可传染的人
    	{
        
    		int xx = x + dx[i];
    		int yy = y + dy[i];
    		if (map[xx][yy] == 1 && vis[xx][yy] == 0 && xx >= 0 && xx < n && yy >= 0 && yy < m)
    		{
        
    			ans[in].x = xx;
    			ans[in].y = yy;
    			in++;
    			vis[xx][yy] = 1;
    		}
    	}
    }
    int main()
    {
        
    	int k,i,j;
    	char s;
    	in = 0, out = 0;
    	scanf("%d %d %d", &n, &m, &k);
    	memset(map, 0, sizeof(map));
    	memset(vis, 0, sizeof(vis));
    	memset(ans, 0, sizeof(ans));
    	for (i = 0; i < n; i++)//构建人群分布
    	{
        
    		getchar();
    		for (j = 0; j < m; j++)
    		{
        
    			scanf("%c", &s);
    			if (s == '*')
    				map[i][j] = 1;
    			else if (s == '#')
    				map[i][j] = 0;
    			else
    			{
        
    				map[i][j] = 1;
    				vis[i][j] = 1;
    				ans[in].x = i;
    				ans[in].y = j;
    				in++;
    			}
    		}
    	}
    	for (i = 0; i < k; i++)
    	{
        
    		int IN = in;//每次循环时的in大小需要定下来，满足此次寻找个数即可，即定义IN变量否则in会一直in++
    		while (IN > out)
    		{
        
    			BFS(ans[out].x, ans[out].y);
    			out++;
    		}
    	}
    	printf("%d\n", in);
    }

[20201127005030767.png_pic_center]: /images/20221120/cbe9095dd16b491a8659ca2ee6308d11.png