当前位置:首页 > 递推 > 正文
NOI2.3-6262流感传染
4080+

题目大意:在一个有n行n列房间的地方,有些房间住人,有些房间空着,有些人得病,有些人没病。疾病会传染给人,而且每天会让周围的人得病,请问第m天有多少人得病?

题目描述

有一批易感人群住在网格状的宿舍区内,宿舍区为n*n的矩阵,每个格点为一个房间,房间里可能住人,也可能空着。在第一天,有些房间里的人得了流感,以后每天,得流感的人会使其邻居传染上流感,(已经得病的不变),空房间不会传染。请输出第m天得流感的人数。

输入

第一行一个数字n,n不超过100,表示有n*n的宿舍房间。
接下来的n行,每行n个字符,’.’表示第一天该房间住着健康的人,’#’表示该房间空着,’@’表示第一天该房间住着得流感的人。
接下来的一行是一个整数m,m不超过100.

输出

输出第m天,得流感的人数

样例输入

5
....#
.#.@.
.#@..
#....
.....
4

样例输出

16

解题思路

不能简单的遍历一般,旁边有病的自己得病,因为有些是刚得病的,他要等到下一天才传染其他人。

用一个矩阵记录各个房间有传染病的时间,一个房间传染另外一个房间,则mp[x][y] = mp[i][j] + 1。传染周围四个邻接,可以预先处理好dx、dy数组。

可以用暴力枚举、递推,复杂度n的三次方;也可以用广搜,复杂度n的平方。

程序实现

上面的代码是枚举递推;下面的代码是广搜递推。

About

坚决不Copy代码!

本文标签:,,,,

NOI2.3-6262流感传染:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!