题目描述】
有一批易感人群住在网格状的宿舍区内，宿舍区为n*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感，（已经得病的不变），空房间不会传染。请输出第m天得流感的人数。
【输入】
第一行一个数字n，n不超过100，表示有n*n的宿舍房间。
接下来的n行，每行n个字符，’.’表示第一天该房间住着健康的人，’#’表示该房间空着，’@’表示第一天该房间住着得流感的人。
接下来的一行是一个整数m，m不超过100。
【输出】
输出第m天，得流感的人数。
【输入样例】
5 ....# .#.@. .#@.. #.... ..... 4
【输出样例】
16
分析：首先思路应该很简单，就是在指定的天数内模拟，把@旁边不是#的格子都改成@。抱着这样轻视的心态，打出了第一版代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char a[105][105]; int n,day,res=0; int dx[4]={1,0,-1,0}; int dy[4]={0,-1,0,1};//四个方向 int main() { cin>>n; getchar(); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>a[i][j]; } getchar(); } cin>>day; for(int i=1;i<day;i++)//天数内模拟 { for(int p=1;p<=n;p++)//遍历 { for(int q=1;q<=n;q++) { if(a[p][q]=='@')//发现流感患者 { for(int k=0;k<4;k++)//向四个方向传染 { if(a[p+dx[k]][q+dy[k]]=='.') a[p+dx[k]][q+dy[k]]='@'; } } } } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(a[i][j]=='@') res++;//最后的感染者数量 } } cout<<res; return 0; }
运行了一下，发现得到的结果格外大，比如上面那个例子，得出的结果竟然是二十多！
我又编写了debug函数，输出每一天的感染情况。我立即发现了问题。
由于程序从上到下，从左到右遍历，只要看见‘@’就执行传染。问题是，这些'@'并不一定都是当天原来的感染者！也有可能是原来的感染者传播后生成的！举个例子：设n=3，初始阵列如下：
1 2 3
1 . @ .
2 . . .
3 . . .
设模拟了一天的情况，则应该变为：
1 2 3
1 @ @ @
2 . @ .
3 . . .
没错吧？可是接着循环，问题就来了。循环找到了点（2,2），发现这里也有一个感染者。于是接着往下“传染”：
1 2 3
1 @ @ @
2 @ @ @
3 . @ .
看到（3，2）又发现一个，于是继续传染：
1 2 3
1 @ @ @
2 @ @ @
3 @ @ @
很明显，最后的结果是，一天之内，9个人全部被感染！然而真实情况是这样吗？正确的做法是，到第二个步骤（只有四个@）时就结束。循环混淆了当天原有的感染者和新感染者。但实际上只要考虑当天原有的感染者才对。新感染者到第二天才会成为“原有的感染者”。
于是，我改了一下。用一个三维数组k[i][m][c]表示第i天区域内第m个原有感染者的位置，c=0表示横坐标，c=1表示纵坐标。扫描完成之后，数组存放了原有感染者的位置，然后在根据这些位置进行“传染”，这样，就不会混淆原有感染者和新感染者了！
第二版AC代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char a[105][105]; short int k[105][10025][2],m=1; int n,day,res=0; int dx[4]={1,0,-1,0}; int dy[4]={0,-1,0,1}; int main() { cin>>n; getchar(); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>a[i][j]; } getchar(); } cin>>day; for(int i=1;i<day;i++) { for(int p=1;p<=n;p++) { for(int q=1;q<=n;q++) { if(a[p][q]=='@') { k[i][m][0]=p; k[i][m][1]=q; m++;//下一位 } } } for(int n=1;n<=m;n++) { for(int dir=0;dir<4;dir++) { if(a[k[i][n][0]+dx[dir]][k[i][n][1]+dy[dir]]=='.') a[k[i][n][0]+dx[dir]][k[i][n][1]+dy[dir]]='@'; } } m=1;//注意重置m，供下一天使用，因为m是指当天的感染者序数而不是全部的。 } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(a[i][j]=='@') res++; } } cout<<res; return 0; }
第二版