A26465. 流感传染
填空题
困难
知识点
题目描述
流感传染
题目描述
有一批易感人群住在网格状的宿舍区内，宿舍区为n*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感，（已经得病的不变），空房间不会传染。请输出第m天得流感的人数。
输入
第一行一个数字n，n不超过100，表示有n*n的宿舍房间。
接下来的n行，每行n个字符，’.’表示第一天该房间住着健康的人，’#’表示该房间着，
’@’表示第一天该房间住着得流感的人。
接下来的一行是一个整数m，m不超过100.
输出
输出第m天，得流感的人数
样例输入
5
…#
.#.@.
.#@…
#…
…
4样例输出
16参考答案
#include <bits/stdc++.h>
using namespace std;
#define N 105
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
//多趟遍历二维数组
int main()
{
char mp[N][N], t[N][N];//t:临时数组
int n, m, ct = 0;
cin >> n;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
cin >> mp[i][j];
cin >> m;
for(int k = 2; k <= m; ++k)//第k天如何传染
{
memset(t, 0, sizeof(t));//对t清空。
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
{
t[i][j] = mp[i][j];
if(mp[i][j] == '.')//如果(i,j)没患病，但周围有病人，就会被传染，否则和原来一样。
{
for(int l = 0; l < 4; ++l)
{
int x = i + dir[l][0], y = j + dir[l][1];
if(x >= 1 && x <= n && y >= 1 && y <= n && mp[x][y] == '@')
t[i][j] = '@';
}
}
}
memcpy(mp, t, sizeof(t));//拷贝t到mp
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(mp[i][j] == '@')
ct++;
cout << ct;
return 0;
}答案解析
// 队列优化
#include <bits/stdc++.h>
using namespace std;
#define N 105
struct Node
{
int x, y, d;//x，y：坐标 d：天数
};
char mp[N][N];
bool vis[N][N];//第i,j位置是否已经被统计过
int n, m, ct;//ct:计数
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
queue<Node> que;//队列 保存刚刚感染的人
int main()
{
cin >> n;//如不吸收本行的换行符，这个换行符会被下面的scanf("%c")读入
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
{
cin >> mp[i][j];
if(mp[i][j] == '@')
que.push(Node{i, j, 1});//感染者入队
}
cin >> m;
while(que.empty() == false)
{
Node u = que.front();
que.pop();
ct++;
if(u.d == m)//这是个第m天患病的人，不再统计m+1天被传染的人
continue;
for(int i = 0; i < 4; ++i)
{
int x = u.x + dir[i][0], y = u.y + dir[i][1], d = u.d + 1;
if(x >= 1 && x <= n && y >= 1 && y <= n && vis[x][y] == false && mp[x][y] == '.')
{
mp[x][y] = '@';
que.push(Node{x, y, d});
}
}
}
printf("%d", ct);
return 0;
}
上一题
下一题