算法刷题【OpenJudge & 编程兔】流感传染
2022-04-27
题目描述
有一批易感人群住在网格状的宿舍区内，宿舍区为n*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感，（已经得病的不变），空房间不会传染。请输出第m天得流感的人数。
输入输出格式
输入格式： 第一行一个数字n，n不超过100，表示有n*n的宿舍房间。
接下来的n行，每行n个字符，’.’表示第一天该房间住着健康的人，’#’表示该房间空着，’@’表示第一天该房间住着得流感的人。
接下来的一行是一个整数m，m不超过100。
输出格式：
输出第m天，得流感的人数。
输入输出样例
In 1
5
....#
.#.@.
.#@..
#....
.....
4Out 1
16思路：数据范围不大（没有具体给出），所以很简单的模拟出来就好了。挨个格子检测如果上下左右有一个前一天感染过的就把他也标记为当天被感染了，最后模拟结束后将标记为当天被感染的改成前一天被感染的标记
有一个要注意的坑：第一个人感染是在第一天，不在第0天，所以要模拟的是m-1次
要说的都在注释里了
#include <bits/stdc++.h>
using namespace std;
int d[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int main() {
int n, m;
char a[200][200];
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) cin >> a[i][j];
cin >> m;
while (--m) { // 共m-1次
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
// 模拟每个格子
if (a[i][j] != '.') continue; // 空格子或已被感染的不管
for (int k = 0; k < 4; k++) {
// 遍历上下左右
if (i + d[k][0] >= 0 && i + d[k][0] < n &&
j + d[k][1] >= 0 && j + d[k][1] < n &&
a[i + d[k][0]][j + d[k][1]] == '@') {
// 向这个方向移动一格在方阵内且该格子住户前一天已经被感染
a[i][j] =
'&'; // 标记为当天被感染：此处若直接标注@会影响他右边或下边的各自判断其上下左右是否有前一天就被感染的
break;
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (a[i][j] == '&') a[i][j] = '@'; // 一天结束，当天感染的变成前一天感染的
}
}
int cnt = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (a[i][j] == '@') cnt++;
cout << cnt << endl;
return 0;
}