【问题的出现】

　　C++一本通在线测评"1191：流感传染",题目要求如下

【题目描述】
有一批易感人群住在网格状的宿舍区内，宿舍区为n*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。在第一天，有些房间里的人得了流感，

以后每天，得流感的人会使其邻居传染上流感，（已经得病的不变），空房间不会传染。请输出第m天得流感的人数。

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

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

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

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

【题目分析】

　　这个题目其实很简单的,就是遍历数组,如果某个房间里住着得流感的人,就去查看其邻居是否有人,有则让人得上流感(可以不考虑是否己是流感患者),于是得到如下代码

//1191：流感传染
#include<iostream>
using namespace std;
char a[102][102];
int n,m,ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)//输入方阵数据
        for(int j=1;j<=n;j++)cin>>a[i][j];
    cin>>m;
    for(int i=2;i<=m;i++)//每天更新人群状态 
        for(int j=1;j<=n;j++)//遍历整个数组 
            for(int k=1;k<=n;k++)
            {
                if(a[j][k]=='@')//如果当前房间里有患流感的人
                {
                    if(a[j-1][k]=='.')a[j-1][k]='@';//邻居若有人,则让其患上流感 
                    if(a[j+1][k]=='.')a[j+1][k]='@';
                    if(a[j][k-1]=='.')a[j][k-1]='@';
                    if(a[j][k+1]=='.')a[j][k+1]='@';
                 } 
             }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) 
            if(a[i][j]=='@')ans++;
    cout<<ans;
    return 0;
}

【初次表现】

　　程序运行,输入样例数据,

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

　　结果显示18(正确结果16)

【错因分析】

　　细细分析出错原因在哪里?--数据更新太过及时.在第一天中,患流感的人只有a[2][4]和a[3][3],a[3][4]是没有患流感的,也就意味着在第二天a[3][5]和a[4][4]应该还是健康的,但通过上述程序的运行,情况变得不一样了.当j=2,k=4时显然a[2][4]是流感患者,他会让a[3][4]以a[2][5]等四人患上流感,同样在第二天中,当j=2,k=5时,第一天的数据中a[2][5]是健康人,不应该有传染性,但由于上一循环中(j=2,k=4)己把a[2][5]修改为@了,就具有传染性了,这就出错了.同样,a[3][4],a[4][3]也会出现类似错误.

【解决办法】

　　办法一:增加一个维度(天数),让两天的数据互不干扰.先把前天的数据复制到当前天,再根据前一天的数据更新被传染人员,代码如下

//1191：流感传染
#include<iostream>
using namespace std;
char a[102][102][102];//第一维度代表天数 
int n,m,ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)cin>>a[1][i][j];
    cin>>m;
    for(int i=2;i<=m;i++)//每天更新人群状态 
    {
        for(int j=1;j<=n;j++)//复制前一天的数据 
            for(int k=1;k<=n;k++)
                a[i][j][k]=a[i-1][j][k];
                 
        for(int j=1;j<=n;j++)//遍历整个数组 
            for(int k=1;k<=n;k++)
            {
                if(a[i-1][j][k]=='@')//如果当前房间里有患流感的人
                {
                    if(a[i-1][j-1][k]=='.')a[i][j-1][k]='@';//邻居若有人,则让其患上流感 
                    if(a[i-1][j+1][k]=='.')a[i][j+1][k]='@';
                    if(a[i-1][j][k-1]=='.')a[i][j][k-1]='@';
                    if(a[i-1][j][k+1]=='.')a[i][j][k+1]='@';
                 } 
             }        
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) 
            if(a[m][i][j]=='@')ans++;
    cout<<ans;
    return 0;
}

　　办法二:让新感染者数据缓冲一天.新感染者的值不直接换成@,而是换成除.和@,#外的字符,当循环正常读到该天数据时再替换为@,代码如下

//1191：流感传染
#include<iostream>
using namespace std;
char a[102][102];
int n,m,ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)cin>>a[i][j];
    cin>>m;
    for(int i=2;i<=m;i++)//每天更新人群状态 
        for(int j=1;j<=n;j++)//遍历整个数组 
            for(int k=1;k<=n;k++)
            {
                if(a[j][k]=='@')//如果当前房间里有患流感的人,邻居若有人,则让其患上流感 
                {
                    if(a[j-1][k]=='.')a[j-1][k]='@';//前两行数据己读过了,直接替换不会出错 
                    if(a[j][k-1]=='.')a[j][k-1]='@';
                    if(a[j+1][k]=='.')a[j+1][k]='h';//先标记为感染而不传染 
                    if(a[j][k+1]=='.')a[j][k+1]='h';
                 }
                if(a[j][k]=='h')a[j][k]='@';//己感染人员标记为感染且可传染 
             }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) 
            if(a[i][j]=='@')ans++;
    cout<<ans;
    return 0;
}

【话题延伸】

　　这一现象也正是在背包问题中,0-1背包和完全背包处理方式只是一个顺序就能改变的原因之一.