1191：流感传染

• 此题是在递推中出现的，但是我没有想到纯递推的做法

  可能BFS也算递推的一种？

题目描述

有一批易感人群住在网格状的宿舍区内，宿舍区为n*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空

着。在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感，（已经得病的不变），

空房间不会传染。请输出第m天得流感的人数。

输入

第一行一个数字n，n不超过100，表示有n*n的宿舍房间。

接下来的n行，每行n个字符，’.’表示第一天该房间住着健康的人，’#’表示该房间空着，’@’表示第一天该房间住着

得流感的人。

接下来的一行是一个整数m，m不超过100。

输出

输出第m天，得流感的人数。

输入样例

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

输出样例

16

思路

• BFS，每感染一个，ans++

• 需要注意的地方是：

  • 邻居指的是 上下左右 四个方向 （我一开始以为八个方向，整了老半天）

  • 图一开始就已经有了第一天感染的人，而且第m天的人数，指的是第m天还没有开始感染的人数

    ​ 一共要循环 m-1 次

代码

#include 
    
     using namespace std;int n,em,ans;char m[110][110];pair
     
       t,tt;queue
      
       
         > v,q;int xx[4]={1,-1,0,0};int yy[4]={0,0,1,-1};int main(){    cin>>n;    for(int i=1;i<=n;++i){        for(int j=1;j<=n;++j){            cin>>m[i][j];            if(m[i][j]=='@'){                t.first = i;                t.second = j;                v.push(t);//把感染的坐标放入队列中                ans++;//先统计第一天中的感染人数            }        }    }    cin>>em;    for(int i=1;i
        
         =1&&ny>=1&&nx<=n&&ny<=n&&m[nx][ny]=='.'){                    tt.first = nx;                    tt.second = ny;                    q.push(tt);//感染一天，就是把v中的所有元素都出队，然后四个方向感染，合适的入到q                    ans++;//直接记录人数                    m[nx][ny] = '@';                }            }        }        while(!q.empty()){//再把q中的元素导入v中，满足（!v.empty()） 继续BFS            v.push(q.front());            q.pop();        }    }    cout<
         
          <