c语言利用递归 解决流感传染问题

Question

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

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

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

样例输入

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

样例输出
19

Answer 1

#include <stdlib.h>
#include <malloc.h>
#include <memory.h>

//感染函数输入参数：
//room: 房间现状
//n:    房间行列数
//p:    感染者所在房间序号
void infect(char *room, int n, int p)
{
if (p<0) return;
if (p>=n*n) return;

int a[4];
a[0]=p-1;
a[1]=p+1;
a[2]=p+n;
a[3]=p-n;
p%=n;
if (p==0) a[0]=-1;
if (p==n-1) a[1]=-1;
if (a[2]>=n*n) a[2]=-1;
if (a[3]<0) a[3]=-1;

for (p=0; p<4; ++p)
{
n=a[p];
if (n==-1) continue;
//如果该房间住着健康的人，则感染
if (room[n]=='.') room[n]='@';
}
}

//用来显示第m天的宿舍状态
void print(const char *room, int n, int m)
{
int i,j;
printf("第%d天宿舍状态：\n",m);
for (j=0; j<n; ++j)
{
for (i=0; i<n; ++i) printf("%c", *room++);
printf("\n");
}

}

int process(const char *filename)
{
int n;      //房间行列数
char *room; //房间
int m;      //m天

FILE *f;
if (NULL==(f=fopen(filename,"r"))) return -1; //文件打开失败

//读取房间行列数
char buf[1000];
if (NULL==fgets(buf, sizeof(buf), f)) return -2; //读取行列数失败
if (1!=sscanf(buf, "%d", &n)) return -2;
if (n<=0) return -3;   //房间行列数n不合法

//读取房间现状
room=(char*)malloc(n*n);  //为房间分配内存
int i;
char *temp;
for (i=0,temp=room; i<n; ++i,temp+=n)
{
if (NULL==fgets(buf, sizeof(buf), f)) 
{
free(room); 
return -4;  //读取读取房间现状有误
} 
memcpy(temp,buf,n);
}

//对房间现状进行合法性分析
for (i=n*n,temp=room; i; --i,++temp)
{
if (*temp=='.') continue;
if (*temp=='@') continue;
if (*temp=='#') continue;
return -5; //房间现状不合法
}

//读取m值
if (NULL==fgets(buf, sizeof(buf), f)) return -6;//读取m失败
if (1!=sscanf(buf, "%d", &m)) return -6; //读取m失败
if (m<0) return -7; //m不合法

fclose(f);

int j;
char *ROOM;  //用来备份房间现状
ROOM=(char*)malloc(n*n);
print(room, n,0);

for (j=0; j<m; ++j)
{
memcpy(ROOM,room,n*n);  //备份房间现状
for (i=n*n,temp=ROOM; i; --i,++temp)
{
if (*temp!='@') continue;
//开始感染前后左右的房间
infect(room, n, temp-ROOM);
}
print(room, n, j+1);
}

for (i=n*n,j=0, temp=room; i; --i, ++temp)
if (*temp=='@') ++j;
printf("%d\n",j);
free(room);
free(ROOM);
return 0;
}

int main(int argc, char* argv[])
{
int ret;
if (argc<=1)
{
printf("用法：infect filename\n");
return 0;
}

ret=process(argv[1]);
switch(ret)
{
case -1: printf("文件%s打开失败。\n",argv[1]); break;
case -2: printf("读取房间行列数失败。\n"); break;
case -3: printf("房间行列数不合法。\n"); break;
case -4: printf("读取读取房间现状有误。\n"); break;
case -5: printf("房间现状不合法。\n"); break;
case -6: printf("读取m失败。\n"); break;
case -7: printf("m不合法。\n"); break;
}
return 0;
}

/*
以下是测试文件内容：假定为test.txt
5
....#
.#.@.
.#@..
#....
.....
4
以下是执行程序后的显示：
第0天宿舍状态：
....#
.#.@.
.#@..
#....
.....
第1天宿舍状态：
...@#
.#@@@
.#@@.
#.@..
.....
第2天宿舍状态：
..@@#
.#@@@
.#@@@
#@@@.
..@..
第3天宿舍状态：
.@@@#
.#@@@
.#@@@
#@@@@
.@@@.
第4天宿舍状态：
@@@@#
.#@@@
.#@@@
#@@@@
@@@@@
19
*/

Answer 2

#include<stdio.h>
#include<stdlib.h>
void fun(char **s,int count,int n);
int main()
{
int n,num;
int i,j;
int count=0;
char **s;
scanf("%d",&n);
while(getchar()!='\n')
continue;
s=(char **)malloc(sizeof(char *)*n); //申请n个指针
for(i=0;i<n;i++)
{
*(s+i)=(char *)malloc(sizeof(char)*n);//每个指针申请n个char字符空间
}
/*****初始化******/
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%c",*(s+i)+j); //第i行第j列的地址
}
while(getchar()!='\n')
continue;
}
scanf("%d",&num); //天数，即递归的层数
fun(s,num,n);
/*****输出显示******/
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if((*(*(s+i)+j))=='@')
count++;
}
}
printf("%d",count);
return 0;
}
void fun(char **s,int count,int n)
{
int i,j;
int m,k;
if(count>0)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(*(*(s+i)+j)=='@')//如果是感染者
{
if((i-1)>=0&&(*(*(s+i-1)+j))!='#'&&(*(*(s+i-1)+j))!='@') //左元素不到左边界且不为空
*(*(s+i-1)+j)='a';
if((i+1)<n&&(*(*(s+i+1)+j))!='#'&&(*(*(s+i+1)+j))!='@') //右元素不到右边界且不为空
*(*(s+i+1)+j)='a';
if((j-1)>=0&&(*(*(s+i)+(j-1)))!='#'&&(*(*(s+i)+(j-1)))!='@') //上元素不到上边界且不为空
*(*(s+i)+(j-1))='a';
if((j+1)<n&&(*(*(s+i)+(j+1)))!='#'&&(*(*(s+i)+(j+1)))!='@') //下元素不到下边界且不为空
*(*(s+i)+(j+1))='a';
}
}
}
#if 0
for(m=0;m<n;m++) //每轮修改前对比
{
for(k=0;k<n;k++)
{

printf("%c",*(*(s+m)+k));
}
printf("\n");
}
printf("\n");
#endif
for(m=0;m<n;m++) //前面标记新感染者为'a'，现在改为@后进入下一轮感染
{
for(k=0;k<n;k++)
{
if((*(*(s+m)+k))=='a')
*(*(s+m)+k)='@';
}
}
#if 0
for(m=0;m<n;m++) //每轮修改后对比
{
for(k=0;k<n;k++)
{

printf("%c",*(*(s+m)+k));
}
printf("\n");
}
printf("\n");
printf("\n");
printf("\n");
#endif

fun(s,count-1,n);
}

}