//ferry.cpp

/*
This is a ferry question!
 missionary
 cannibal
 ship
 用一個鏈表表示要搜索的狀態集 
 用一個鏈表表示解狀態集
 啟發函數為f(x)=h(x)+g(x)
 h(x)=M+C-2D
 g(x)=深度

 search :待搜索的鏈表
 finished: 完成搜索的鏈表
 route:     路徑鏈表

*/

#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>


struct FerryNode                 //用來保存節點的狀態
{
	int missionary;              //左岸傳教士數目
	int cannibal;                //左岸野人數目
	int side;                   //船在左岸為1,在右岸為0
	int depth;
	FerryNode *father;          //父節點
	FerryNode *next;            
};

FerryNode *SEARCH=NULL,*FINISHED=NULL,*ROUTE=NULL;
int MISSIONARY=0,CANNIBAL=0,SHIP=0;
int SUCCESS=2;


int main()
{

	void setFerry();                               //設置渡河問題的函數
	void shipFerry();                               //渡河函數
	void printFerry();                             //打印渡河路徑
	//void printLink(FerryNode *);                   //打印鏈表函數

	cout<<endl<<"This is a ferry question."<<endl;
	cout<<"Program begin......"<<endl;

	

	setFerry();

	if((MISSIONARY<=0)||(SHIP<=1))
	{
		cout<<"不存在解答!"<<endl;
		cout<<"The program is finished."<<endl;
		getch();
		return 0;
	}

    shipFerry();
	printFerry();

	cout<<endl<<"The ferry program is finished!"<<endl;

	getch();

	return 0;
}

//設置渡河問題的函數
void setFerry()
{
	cout<<"清輸入傳教士的數目(野人的數目與傳教士一樣),要求>0:";
	cin>>MISSIONARY;
	//cout<<"\n清輸入野人的數目:"
	//cin>>CANNIBAL;
	CANNIBAL=MISSIONARY;
	cout<<"\n清輸入小船一次最多載客數,要求>1:";
	cin>>SHIP;

	//初始化鏈表
	SEARCH = new FerryNode;
	SEARCH->father = NULL;
    SEARCH->next = NULL;
	
	FINISHED = new FerryNode;
	FINISHED->father = NULL;
	FINISHED->next = NULL;

	ROUTE = new FerryNode;
	ROUTE->father = NULL;
	ROUTE->next = NULL;

	FerryNode *NewSearch = new FerryNode;
	NewSearch->missionary = MISSIONARY;
	NewSearch->cannibal = CANNIBAL;
	NewSearch->side = 1;
	NewSearch->depth = 0;
	NewSearch->father = NULL;
	NewSearch->next = NULL;
	SEARCH->next = NewSearch;

	FerryNode *NewRoute = new FerryNode;
	NewRoute->missionary = 0;
	NewRoute->cannibal = 0;
	NewRoute->side = 0;
	NewRoute->father =NULL;
	NewRoute->next = NULL;
	ROUTE->father = NewRoute;	

}

void  shipFerry()
{
	void createNode(FerryNode *);

	while(SUCCESS==2)
	{
		FerryNode *SearchNode = SEARCH->next;
		if(SearchNode!=NULL)
			{
				if((SearchNode->missionary+SearchNode->cannibal<=SHIP)&&(SearchNode->side ==1))
					{
						ROUTE->father->father = SearchNode;
						SUCCESS=1;
					}
				else
					{
						SEARCH->next = SearchNode->next;
					    SearchNode->next = FINISHED->next;
						FINISHED->next = SearchNode;
						createNode(SearchNode);
					}
				}
		else
		  SUCCESS=0;
	}



	
	

}

void printFerry()
{
	if(SUCCESS==0)
	{
		cout<<"There is no answer!"<<endl;
		return;
	}


	cout<<"This is the route:"<<endl;
	FerryNode *SearchNode = ROUTE ;
	FerryNode *ps=ROUTE;
	int i=1;
	while(ROUTE->father!=NULL )
	{

        while(SearchNode->father !=NULL)
		{
			ps = SearchNode;
            SearchNode = SearchNode->father;


		}


		cout<<"<"<<SearchNode->missionary<<","<<SearchNode->cannibal<<","<<SearchNode->side<<">   ";
		ps->father = NULL;

		if(i%5==0)
			cout<<endl;
		i=i+1;

		SearchNode = ROUTE ;
	    ps=ROUTE;

	}
	cout<<endl;


}

void createNode(FerryNode *SearchNode)
{
	int m,c,s,d;
	int findFerry(int m,int c,int s);
	void insertFerry(int m,int c,int s,int d,FerryNode *);
	m = SearchNode->missionary ;
	c = SearchNode->cannibal ;
	s = SearchNode->side ;
	d = SearchNode->depth ;


//	cout<<"\n測試"<<m<<c<<s;

	if(s== 1)
	{
		for(int i=0;i<=SHIP;i++)
			for(int j=0;j<=SHIP-i;j++)
			{
				if(i+j>0)
					if(((i<=m) && (j<=c) && (m-i >= c-j) &&(MISSIONARY-m+i >= CANNIBAL-c+j))||((i<=m)&&(j<=c)&&(m-i==0))||((i<=m)&&(j<=c)&&(MISSIONARY-m+i==0)))
					{
						if(findFerry(m-i,c-j,0)==0)
							insertFerry(m-i,c-j,0,d+1,SearchNode);						

					}					


			}

	}

	else
	{
		for(int i=0;i<=SHIP;i++)
			for(int j=0;j<=SHIP-i;j++)
			{
				if(i+j>0)
					if(((i<=MISSIONARY-m)&&(j<=CANNIBAL-c)&&(m+i>=c+j)&&(MISSIONARY-m-i>=CANNIBAL-c-j))||((m==0)&&(i==0)&&(j<=CANNIBAL-c))||((i<=MISSIONARY-m)&&(j<=CANNIBAL-c)&&(MISSIONARY-m-i==0)))
					{
						if(findFerry(m+i,c+j,1)==0)
							insertFerry(m+i,c+j,1,d+1,SearchNode);
					}

			}
	}




}

int findFerry(int m,int c,int s)
{
	FerryNode *ps = SEARCH->next ;
	FerryNode *pf = FINISHED->next ;

    while(ps!= NULL)
	{
		if((m==ps->missionary )&&(c==ps->cannibal )&&(s==ps->side ))
			return 1;
		ps= ps->next ;
	}
    
    while(pf!= NULL)
	{
		if((m==pf->missionary )&&(c==pf->cannibal )&&(s==pf->side ))
			return 1;
		pf= pf->next ;
	}

	return 0;


}

void insertFerry(int m,int c,int s,int d,FerryNode *SearchNode)
{

	FerryNode *ps = SEARCH->next ;
	FerryNode *pb=SEARCH;
	while(ps!=NULL)
	{
       if((m+c-2*s+d) <= (ps->missionary+ps->cannibal-2*ps->side+ps->depth ) )
	   {
		   FerryNode *NewNode = new FerryNode;
		   NewNode->missionary = m;
		   NewNode->cannibal = c;
		   NewNode->side = s;
		   NewNode->depth = d;
		   NewNode->next = ps ;
		   NewNode->father = SearchNode;
		   pb->next = NewNode;
		   
		   return;
	   }
	   pb = ps;
	   ps=ps->next ;
	}


	FerryNode *nd = new FerryNode;
	nd->missionary = m;
	nd->cannibal = c;
	nd->side =s;
	nd->depth = d;
	nd->next = NULL;
	nd->father = SearchNode;
	pb->next = nd;

}

/*
void printLink(FerryNode *pn)
{
	cout<<"\nThis is a link....\n";
	pn=pn->next ;
    while(pn!=NULL)
	{
		cout<<"<"<<pn->missionary <<","<<pn->cannibal <<","<<pn->side <<","<<pn->depth<<">  ";
		pn=pn->next ;
	}


}
*/