总时间限制:
1000ms
内存限制:
65536kB
描述
有一批易感人群住在网格状的宿舍区内，宿舍区为n*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感，（已经得病的不变），空房间不会传染。请输出第m天得流感的人数。
输入
第一行一个数字n，n不超过100，表示有n*n的宿舍房间。
接下来的n行，每行n个字符，’.’表示第一天该房间住着健康的人，’#’表示该房间空着，’@’表示第一天该房间住着得流感的人。
接下来的一行是一个整数m，m不超过100.
输出
输出第m天，得流感的人数
样例输入
5
....#
.#.@.
.#@..
#....
.....
4
样例输出
16
题解：
没有用DFS或者BFS，而直接用的模拟。用一个mark来记录本次被感染的人标记的数字为明天的日期，例如今天是第一天，那么将今天感染的人标记为2，即第二天将进行操作的人最后再遍历一遍统计‘@’的数量
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#define MAXA 200
typedef long long LL;
using namespace std;
int N,M,cnt,mark[MAXA][MAXA];
char House[MAXA][MAXA];
int main() {
scanf("%d",&N);
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++) {
cin >> House[i][j];
if(House[i][j] == '@')
mark[i][j] = 1;
}
scanf("%d",&M);
for(int k=1;k<M;k++)
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
if(House[i][j] == '@' && mark[i][j] == k) {
if(House[i-1][j] == '.') {
House[i-1][j] = '@';
mark[i-1][j] = k + 1;
}
if(House[i+1][j] == '.') {
House[i+1][j] = '@';
mark[i+1][j] = k + 1;
}
if(House[i][j-1] == '.') {
House[i][j-1] = '@';
mark[i][j-1] = k + 1;
}
if(House[i][j+1] == '.') {
House[i][j+1] = '@';
mark[i][j+1] = k + 1;
}
mark[i][j] = 0;
}
for(int i=1;i<=N;i++) {
for(int j=1;j<=N;j++) {
if(House[i][j] == '@')
cnt++;
}
}
printf("%d",cnt);
}
