NOI2.3-6262流感传染
5221+
作者：crxis 发布：2017-06-25 分类：递推
题目大意：在一个有n行n列房间的地方，有些房间住人，有些房间空着，有些人得病，有些人没病。疾病会传染给人，而且每天会让周围的人得病，请问第m天有多少人得病？
题目描述
有一批易感人群住在网格状的宿舍区内，宿舍区为n*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感，（已经得病的不变），空房间不会传染。请输出第m天得流感的人数。
输入
第一行一个数字n，n不超过100，表示有n*n的宿舍房间。
接下来的n行，每行n个字符，’.’表示第一天该房间住着健康的人，’#’表示该房间空着，’@’表示第一天该房间住着得流感的人。
接下来的一行是一个整数m，m不超过100.
接下来的n行，每行n个字符，’.’表示第一天该房间住着健康的人，’#’表示该房间空着，’@’表示第一天该房间住着得流感的人。
接下来的一行是一个整数m，m不超过100.
输出
输出第m天，得流感的人数
样例输入
5
....#
.#.@.
.#@..
#....
.....
4
样例输出
16
解题思路
不能简单的遍历一般，旁边有病的自己得病，因为有些是刚得病的，他要等到下一天才传染其他人。
用一个矩阵记录各个房间有传染病的时间，一个房间传染另外一个房间，则mp[x][y] = mp[i][j] + 1。传染周围四个邻接，可以预先处理好dx、dy数组。
可以用暴力枚举、递推，复杂度n的三次方；也可以用广搜，复杂度n的平方。
程序实现
上面的代码是枚举递推；下面的代码是广搜递推。
