信息学奥赛一本通T1191：流感传染

【题目描述】

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

【输入】

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

【输出】

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

【输入样例】

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

【输出样例】

16

【源程序】

#include<iostream>
#include<cstring>
using namespace std;
char s[110];
int a[110][110];
struct node{
    int r;//r行
    int c;//c列
    int d;//d天
}q[10100];
int nextt[][2]={{-1,0},{1,0},{0,-1},{0,1}};
int main()
{
    int n,m;
    int h=1,t=1;
    int r,c,d;
    int nr,nc,cnt=0;
    int i,j;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>s;
        for(j=0;j<n;j++)
            if(s[j]=='.')
                a[i][j]=0;
            else if(s[j]=='@')
            {
                a[i][j]=1;
                q[t].r=i;
                q[t].c=j;
                q[t].d=1;
                t++;
            }
            else if(s[j]=='#')
                a[i][j]=2;
    }
    cin>>m;
    while(h<t)
    {
        r=q[h].r;
        c=q[h].c;
        d=q[h].d;
        if(d==m)
            break;
        for(i=0;i<4;i++)
        {
            nr=r+nextt[i][0];
            nc=c+nextt[i][1];
            if(a[nr][nc]==0&&0<=nr&&nr<n&&0<=nc&&nc<n)
            {
                q[t].r=nr;
            	q[t].c=nc;
                q[t].d=d+1;
                a[nr][nc]=1;
                 t++;
            }
        }
        h++;
    }
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(a[i][j]==1)
                cnt++;
    cout<<cnt<<endl;
    return 0;
}

信息学奥赛一本通T1191：递推算法 流感传染 归属于 递推算法，更多同类题解源程序见：递推算法 和 流感传染