#include<iostream.h>
#define MaxNumVertices 10  //最大頂點數
typedef enum {FALSE,TRUE}Boolean;
typedef struct  //圖的頂點類型
{
	int Farmer,Wolf,Sheep,Veget;
}VexType;
typedef struct
{
	int VertexNum,CurrentEdges;  //圖的當前頂點數和邊數
    VexType VerticesList[MaxNumVertices];  //頂點向量（代表頂點）
	int Edge[MaxNumVertices][MaxNumVertices];//鄰接矩陣
    //用于存儲圖中的邊，其矩陣元素個數取決于頂點個數，與邊數無關
}AdjGraph;  //定義圖的鄰接矩陣存儲結構
Boolean visited[MaxNumVertices];  //對已訪問的頂點進行標記（圖的遍歷）
int path[MaxNumVertices];  
//保存DFS搜索到的路徑，即與某頂點到下一頂點的路徑

int locate(AdjGraph *G,int F,int W,int S,int V)
//查找頂點（F，W，S，V）在頂點向量中的位置
{  
	int i;
	for(i=0;i<G->VertexNum;i++)
		if(G->VerticesList[i].Farmer==F && G->VerticesList[i].Wolf==W &&
			G->VerticesList[i].Sheep==S && G->VerticesList[i].Veget==V)
			return(i);  //返回當前位置
		return (-1);  //沒有找到此頂點
}

int is_safe(int F,int W,int S,int V)
//判斷目前的（F，W，S，V）是否安全
{
	if(F!=S && (W==S||S==V))
		return (0); 
	//當農夫與羊不在一起時，狼與羊或羊與白菜在一起是不安全的
	else   //否則安全
		return (1);  //安全返回1
}

int is_connected(AdjGraph *G,int i,int j)
//判斷狀態i與狀態j之間是否可轉換
{
	int k=0;
	if(G->VerticesList[i].Wolf!=G->VerticesList[j].Wolf)
		k++;
	if(G->VerticesList[i].Sheep!=G->VerticesList[j].Sheep)
		k++;
	if(G->VerticesList[i].Veget!=G->VerticesList[j].Veget)
		k++;
	if(G->VerticesList[i].Farmer!=G->VerticesList[j].Farmer && k<=1)
    //以上三個條件不同時滿足兩個且農夫狀態改變時，返回真
    //也即農夫每次只能帶一件東西過橋
		return(1);
	else 
		return(0);
}

void CreateG(AdjGraph*G)
{
	int i,j,F,W,S,V;
	i=0;
	for(F=0;F<=1;F++)  //生成所有安全的圖的頂點
		for(W=0;W<=1;W++)
			for(S=0;S<=1;S++)
				for(V=0;V<=1;V++)
					if(is_safe(F,W,S,V))
					{
						G->VerticesList[i].Farmer=F;
						G->VerticesList[i].Wolf=W;
						G->VerticesList[i].Sheep=S;
						G->VerticesList[i].Veget=V;
						i++;
					}
	G->VertexNum=i;
	for(i=0;i<G->VertexNum;i++)  //鄰接矩陣初始化即建立鄰接矩陣
		for(j=0;j<G->VertexNum;j++)
			if(is_connected(G,i,j))
				G->Edge[i][j]=G->Edge[j][i]=1;
	//狀態i與狀態j之間可轉化，初始化為1，否則為0
			else
				G->Edge[i][j]=G->Edge[j][i]=0;
	return;
}

void print_path(AdjGraph *G,int u,int v)
//輸出從u到v的簡單路徑，即頂點序列中不重復出現的路徑
{
	int k;
	k=u;
	while(k!=v)
	{
	cout<<"("<<G->VerticesList[k].Farmer<<","<<G->VerticesList[k].Wolf
		<<","<<G->VerticesList[k].Sheep<<","<<G->VerticesList[k].Veget<<")";
	cout<<endl;
	k=path[k];
	}
	cout<<"("<<G->VerticesList[k].Farmer<<","<<G->VerticesList[k].Wolf
		<<","<<G->VerticesList[k].Sheep<<","<<G->VerticesList[k].Veget<<")";
	cout<<endl;
}

void DFS_path(AdjGraph *G,int u,int v)
//深度優先搜索從u到v的簡單路徑
//DFS--Depth First Search
{
	int j;
	visited[u]=TRUE;  //標記已訪問過的頂點
	for(j=0;j<G->VertexNum;j++)
		if(G->Edge[u][j] && !visited[j] && !visited[v])
		{
			path[u]=j;
			DFS_path(G,j,v);
		}
}

void main()
{
	int i,j;
	AdjGraph graph;
	CreateG(& graph);
	for(i=0;i<graph.VertexNum;i++)
		visited[i]=FALSE;  //置初值
	i=locate(&graph,0,0,0,0);
	j=locate(&graph,1,1,1,1);
	DFS_path(&graph,i,j);
	if(visited[j])
		print_path(&graph,i,j);
	return;
}