#include <stdio.h>
#include <stdlib.h>
#define maxloop 100    //最大層數，對于不同的擴展方法自動調整取值#define pristnum 3#define slavenum 3struct SPQ{	int sr,pr;             //船運行一個來回后河右岸的野人、傳教士的人數 	int sl,pl;             //船運行一個來回后河左岸的野人、傳教士的人數 	int ssr,spr;           //回來（由左向右時）船上的人數	int sst,spt;           //去時（由右向左時）船上的人數	int loop;               //本結點所在的層數                 	struct SPQ *upnode ,*nextnode;//本結點的父結點和同層的下一個結點的地址}spq;  int loopnum;//記錄總的擴展次數int openednum;//記錄已擴展節點個數int unopenednum;//記錄待擴展節點個數int resultnum;struct SPQ *opened;struct SPQ *oend;struct SPQ *unopened;          struct SPQ *uend;struct SPQ *result;void initiate();
void releasemem();void showresult();void addtoopened(struct SPQ *ntx);int search();
void goon();int stretch(struct SPQ* ntx);
void recorder();void main(){	int flag;       //標記擴展是否成功	
	for( ; ; )	{		initiate();		flag = search ();		if(flag == 1)		{			recorder();			releasemem();			showresult();
			goon();		}		else		{			printf("無法找到符合條件的解");
			releasemem();			goon();
		}	}}void initiate(){	int x;
	char choice;
	uend = unopened = (struct SPQ*)malloc(sizeof(spq));	if(uend==NULL)
	{
		printf("\n內存不夠！\n");
		exit(0);
	}	unopenednum=1;	openednum=0;	unopened -> upnode = unopened;       //保存父結點的地址以成鏈表	unopened -> nextnode = unopened;	unopened -> sr = slavenum;	unopened -> pr = pristnum;	unopened -> sl = 0;	unopened -> pl = 0;	unopened -> sst = 0;	unopened -> spt = 0;	unopened -> ssr = 0;	unopened -> spr = 0;	unopened -> loop = 0;	printf("題目：設有n個傳教士和m個野人來到河邊，打算乘一只船從右岸到左岸去。\n");
	printf("該船的負載能力為兩人。在任何時候，如果野人人數超過傳教士人數，野人\n");
	printf("就會把傳教士吃掉。他們怎樣才能用這條船安全的把所有人都渡過河去?\n");
	printf("\n默認的n、m值皆為3\n");
    for(;;)
	{
		printf("\n是否修改？(Y/N)");
		scanf("%s",&choice);
		choice=toupper(choice);
		if(choice=='Y')
		{			
			printf("\n請輸入傳教士人數");
			for(;;)
			{
				scanf("%d",&x);
				if(x>0)	
				{
					unopened -> pr = x;
					break;
				}
				else printf("\n輸入值應大于0！\n請重新輸入");
			}
			printf("\n請輸入野人人數");
			for(;;)
			{
				scanf("%d",&x);
				if(x>0)
				{
					unopened -> sr = x;
					break;
				}
				else printf("\n輸入值應大于0！\n請重新輸入");
			}	
			break;
		}
		if(choice=='N')break;
	}	}int search(){	int flag;	struct SPQ *ntx;               //提供將要擴展的結點的指針	for( ; ; )	{		ntx = unopened;        //從待擴展鏈表中提取最前面的一個		if(ntx->loop == maxloop)			return 0; 		addtoopened(ntx);       //將ntx加入已擴展鏈表，并將這個節點從待擴展鏈表中去掉
		flag = stretch(ntx);    //對ntx進行擴展,返回-1,0,1		if(flag == 1)			return 1; 			}}int stretch(struct SPQ *ntx){	int fsr , fpr ; //在右岸上的人數	int fsl , fpl ; //在左岸上的人數	int	sst , spt ; //出發時在船上的人數	int ssr , spr ; //返回時船上的人數	struct SPQ *newnode;	for (sst = 0 ; sst <=  2 ; sst++) //討論不同的可能性并判斷是否符合條件	{		fsr = ntx -> sr;		fpr = ntx -> pr;		fsl = ntx -> sl;		fpl = ntx -> pl;		if ((sst <=  fsr) && (( 2 - sst) <=  fpr))//滿足人數限制		{			spt = 2 - sst;			fsr = fsr - sst;			fpr = fpr - spt;			if((fpr ==  0) && (fsr ==  0))//搜索成功			{ 				newnode = (struct SPQ*) malloc (sizeof(spq));
				if(newnode==NULL)
				{
					printf("\n內存不夠！\n");
					exit(0);
				}				newnode -> upnode = ntx;       //保存父結點的地址以成鏈表				newnode -> nextnode = NULL;				newnode -> sr = 0;				newnode -> pr = 0;				newnode -> sl = opened -> sr;				newnode -> pl = opened -> pr;				newnode -> sst = sst;				newnode -> spt = spt;				newnode -> ssr = 0;				newnode -> spr = 0;				newnode -> loop = ntx -> loop + 1;				oend -> nextnode = newnode;				oend = newnode;				openednum++;				return 1;			}   			else if ((fpr - fsr) * fpr >= 0) //判斷是否滿足傳教士人數必須大于或等于野人人數			{				fsl = fsl + sst;				fpl = fpl + spt;				for (ssr = 0 ; ssr <= 1 ; ssr++)                  //返回				{					int ffsl , ffpl;					if ((ssr <= fsl) && ((1 - ssr) <= fpl))					{						spr = 1 - ssr;						ffsl = fsl - ssr;						ffpl = fpl - spr;						if ((ffpl - ffsl) * ffpl >= 0)						{	//若符合條件則分配內存并付值								int  ffsr , ffpr;							ffsr = fsr + ssr;							ffpr = fpr + spr;							                        							newnode = (struct SPQ*) malloc (sizeof(spq));
							if(newnode==NULL)
							{
								printf("\n內存不夠！\n");
								exit(0);
							}							newnode -> upnode = ntx;       //保存父結點的地址以成鏈表							newnode -> sr = ffsr;							newnode -> pr = ffpr;							newnode -> sl = ffsl;							newnode -> pl = ffpl;							newnode -> sst = sst;							newnode -> spt = spt;							newnode -> ssr = ssr;							newnode -> spr = spr;							newnode -> loop = ntx -> loop + 1;							uend -> nextnode = newnode;							uend = newnode;							unopenednum++;																					}					}				}			}		}	} 	return 0;}void addtoopened(struct SPQ *ntx){	unopened = unopened -> nextnode;
	unopenednum--;
	if (openednum == 0 )		oend = opened = ntx;	oend -> nextnode = ntx;	oend = ntx;	openednum++;}void recorder(){	int i , loop;
	struct SPQ *newnode;
	struct SPQ *ntx;
	loop = oend -> loop;
	ntx = oend;	resultnum = 0;	for( i = 0 ; i <= loop ; i++ )	{		newnode = (struct SPQ*) malloc (sizeof(spq));
		if(newnode==NULL)
		{
			printf("\n內存不夠！\n");
			exit(0);
		}		newnode -> sr = ntx -> sr;		newnode -> pr = ntx -> pr;		newnode -> sl = ntx -> sl;		newnode -> pl = ntx -> pl;		newnode -> sst = ntx -> sst;		newnode -> spt = ntx -> spt;		newnode -> ssr = ntx -> ssr;		newnode -> spr = ntx -> spr;
		newnode -> nextnode = NULL;		ntx = ntx -> upnode;						if(i == 0)			result = newnode;		newnode -> nextnode = result;		result = newnode;		resultnum++;	}}void releasemem(){	int i;	struct SPQ* nodefree;	for ( i = 1 ; i < openednum ; i++ )	{		nodefree = opened;		opened = opened -> nextnode;		free(nodefree);	}	for ( i = 0 ; i < unopenednum ; i++ )	{		nodefree = unopened;		unopened = unopened -> nextnode;		free(nodefree);	}}void showresult(){	int i;
    int fsr , fpr ; //在右岸上的人數
	int fsl , fpl ; //在左岸上的人數
	struct SPQ* nodefree;
	printf("%d個傳教士",result -> pr);
	printf("%d個野人",result -> sr);    printf("%d個傳教士",result -> pl);
    printf("%d個野人",result -> sl);	for ( i = 1 ; i < resultnum ; i++ )	{		nodefree = result;		result = result -> nextnode;		free(nodefree);		printf("\n\n\t左岸人數 船上人數及方向 右岸人數\n");
		printf("第%d輪\n",i);
		fpl = result -> pl - result -> spt + result -> spr;
		fpr = result -> pr - result -> spr;
		fsl = result -> sl - result -> sst + result -> ssr;
        fsr = result -> sr - result -> ssr;
		printf("傳教士%8d%8d\t<-\t%8d\n",fpl,result -> spt,fpr);
		printf("野  人%8d%8d\t<-\t%8d\n",fsl,result -> sst,fsr);
		printf("傳教士%8d%8d\t->\t%8d\n",result -> pl,result -> spr,result -> pr - result -> spr);
		printf("野  人%8d%8d\t->\t%8d\n",result -> sl,result -> ssr,result -> sr - result -> ssr);
	}	printf("\n全體傳教士和野人全部到達對岸");	free(result);
}void goon()
{
	char choice;
	for(;;)
	{
		printf("是否繼續？(Y/N)\n");
	    scanf ("%s" , &choice);
		choice=toupper(choice);
		if(choice=='Y')break;
		if(choice=='N')exit(0);
	}
}