SDUT 4783 病毒扩散

病毒扩散"/>

SDUT 4783 病毒扩散

Description

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

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

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

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

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

Input

4 4 2
****
*@**
**##
**#*

Output

12

bfs 注意有多个起点

#include <iostream>
#include <bits/stdc++.h>using namespace std;
int n, m, k;
int countt;
char a[1010][1010];
int mark[1010][1010];
bool vis[1010][1010];
int step[][2]= {{1,0}, {0,-1}, {-1,0}, {0,1}, {1,1}, {-1,1}, {1,-1}, {-1,-1}};
struct node
{int x;int y;int deep;
};
void bfs(int xx,int yy)
{node now, next;memset(vis, false, sizeof(vis));queue<node>q;now.x=xx;now.y=yy;now.deep=1;mark[xx][yy]=1;q.push(now);while(!q.empty()){now = q.front();q.pop();if(now.x<0||now.x>=n||now.y<0||now.y>=m)continue;for(int i=0;i<8;i++){next.x = now.x + step[i][0];next.y = now.y + step[i][1];next.deep = now.deep + 1;if(!vis[next.x][next.y]&&a[next.x][next.y]!='#'){vis[next.x][next.y]=true;mark[next.x][next.y]=min(next.deep, mark[next.x][next.y]);q.push(next);}}}
}
int main()
{memset(mark, 0x3f3f3f3f, sizeof(mark));countt= 0;cin>>n>>m>>k;int i, j;for(i=0;i<n;i++){scanf("%s", a[i]);}for(i=0;i<n;i++){for(j=0;j<m;j++){if(a[i][j]=='@'){bfs(i, j);}}}for(i=0;i<n;i++){for(j=0;j<m;j++){if(mark[i][j]<=k+1)countt++;}}
//    for(i=0;i<n;i++)
//    {
//        for(j=0;j<m;j++)
//        {
//            printf("%d ", mark[i][j]);
//        }
//        printf("\n");
//    }printf("%d\n", countt);return 0;
}
//5 5 3
//*****
//*@***
//**###
//*@#*#
//****#

vis数组保存在某个bfs里某个点有没有走过 mark保存多个起点中距离此店最近的那个