传教士与野人渡河问题

#includestdio.h#includemalloc.h#includestdlib.htypedefstruct{intxds;//传道士intyr;//野人intcw;//船位}DataType;DataTypefa[50000];typedefstructnode{DataTypedata;structnode*son;structnode*bro;structnode*par;structnode*next;}Ltable;voidLtableinit(Ltable**head)//初始化邻接表的操作{*head=(Ltable*)malloc(sizeof(Ltable));//动态分配空间(*head)-son=NULL;(*head)-bro=NULL;(*head)-par=NULL;(*head)-next=NULL;}voidinsertson(Ltable*head,DataTypex)//在邻接表中插入儿子结点的操作{Ltable*q,*s;q=(Ltable*)malloc(sizeof(Ltable));q-data=x;head-son=q;s=head;while(s-next!=NULL)s=s-next;q-par=head;q-son=NULL;q-bro=NULL;s-next=q;q-next=NULL;}voidinsertbro(Ltable*head,DataTypex)//在邻接表中插入兄弟结点的操作，所有的兄弟结点都指向//他们右边的结点；{Ltable*q,*s;q=(Ltable*)malloc(sizeof(Ltable));s=head-son;q-data=x;//while(s-bro!=NULL)////s=s-bro;while(NULL!=s-next)s=s-next;s-bro=q;s-next=q;q-next=NULL;q-bro=NULL;q-par=head;q-son=NULL;}intfindfa(DataTypex,intn)//生成在船上修道士仍安全的几种情况；n为船的最大装载人数{inti=0,a,b,t=0;if(x.cw)//船位为1{a=0;b=n-a;//b为传入参数n(最多过河人数),a为0while(a+b=1)//a等于0，b=n-t,即循环n次{t++;//t初值为0while(b=0)//第一次循环n+1次，第二次循环n次，。。。1,{fa[i].xds=a;//i初值为0，修道士人数等于a，a初值为0(每次初值都为0)fa[i].yr=b;//野人等于b,b初值为参数n,最后为0i++;a++;b--;//}a=0;b=n-a-t;//t初值为1}}//如果船位为1，占用n+1+n+。。。+1个数组（(n+2)*(n+1)/2）else{a=1;b=0;t=0;while(a+b=n)//a初值为1，b初值为0(每次)，循环n次{t++;//初值为0while(a=0)//a初值为1，2，3。。。n(每次循环n+1次){fa[i].xds=a*(-1);//i初值为0fa[i].yr=b*(-1);//b初值为0(每次进入循环时)i++;a--;b++;}a=fa[0].xds*(-1)+t;//t初值为1，fa[0].xds为-1,即a=1+tb=0;}//同样产生n+1+n+。。。+1个数组（(n+2)*(n+1)/2）}returni;//两种情况返回的都为（(n+2)*(n+1)/2）}intjiancha(DataTypex,intn)//安全性检测，检查当前情况下，修道士是否安全{if((x.xds=x.yr||x.xds==0)&&((n-x.xds)=(n-x.yr)||x.xds==n)&&x.xds=0&&x.xds=n&&x.yr=0&&x.yr=n)//未检测在船上的情况return1;elsereturn0;}voidprint(Ltable*q,Ltable*p)//打印安全渡河的过程{DataTypea[100];inti=1;a[0].cw=0;a[0].xds=0;a[0].yr=0;while(q!=p){a[i++]=q-data;q=q-par;//回其父结点}while((--i)-1)//最头上的父结点数组下标{printf((%d%d%d),a[i].xds,a[i].yr,a[i].cw);}printf(渡河成功!\n);}voidwork(Ltable*p,intn,intc){Ltable*q,*t;DataTypetem;inti,flag,flag1,g=0,j,count=0;q=p-son;while(q!=NULL){flag=0;j=findfa(q-data,c);//船的位置和最多搭乘人数for(i=0;ij;i++)//循环j次{tem.xds=q-data.xds-fa[i].xds;tem.yr=q-data.yr-fa[i].yr;tem.cw=1-q-data.cw;t=q;if(jiancha(tem,n))//安全的状态，n为最初人数{flag1=1;while(t!=p)//p传入的参数{if(tem.xds==t-data.xds&&tem.yr==t-data.yr&&tem.cw==t-data.cw)//和状态data为同一个状态{flag1=0;break;}t=t-par;}if(flag1==1){if(flag==0){insertson(q,tem);flag=1;}elseinsertbro(q,tem);if(tem.xds==0&&tem.yr==0&&tem.cw==0)//下一个状态为（0，0，0）q为倒数第二个状态{print(q,p);count++;}}}}q=q-next;}if(count==0)printf(无法成功渡河!\n);elseprintf(有%d种渡河方式。\n,count);}intmain(){Ltable*p;DataTypetem;intm,n,c;Ltableinit(&p);//初始化邻接表;while(1){printf(请输入传教士数目：);scanf(%d,&n);printf(请输入野人数目：);scanf(%d,&m);if(n==0)break;printf(请输入船可容纳的人数:);scanf(%d,&c);tem.xds=n;tem.yr=m;tem.cw=1;insertson(p,tem);//将初始状态作为头结点的孩子结点；work(p,n,c);//进行广度搜索；}return1;}