#include
#include
#define?TRUE?1
#define?FALSE?0
#define?MAXSIZE?16
#define?INFINTITY?65535
using?namespace?std;
int?visited[MAXSIZE];
int?ray[MAXSIZE];?
int?bay[MAXSIZE][MAXSIZE];//存儲???遍歷的節(jié)點?
int?sum?=0;		//下標?
int?sums?=0;	//下標?
int?k=0;	???//記錄數(shù)組的長度
int?step=0;??//步驟?
typedef?int?EdgeType;?//圖?
typedef?int?Status;	//創(chuàng)建一個棧用?
typedef?int?SElemType;//棧?
typedef?struct
{
	SElemType?*base;
	SElemType?*top;
	int?stacksize;
}SqStack;?
typedef?struct{
	int?farmer;
????int?wolf;
????int?sheep;
????int?cabbage;
}status;
typedef?struct
{
????int?stanum;?????????????//頂點個數(shù)
????status?vexs[MAXSIZE];???//儲存頂點數(shù)組
????EdgeType?arc[MAXSIZE][MAXSIZE];??//鄰接矩陣權(quán)值
}MGraph;
Status?InitStak_Sq（SqStack?&S）{
	S.base=new?SElemType[100];
	if（!S.base）{
		exit（0）;
	}
	S.top=S.base;
	S.stacksize=100;
	return?0;
}
int?Push_Sq（SqStack?&Sint?e）{
	if（S.top-S.base==S.stacksize）{
		return?-1;
	}
	*S.top++=e;
	return?0;
}
int?Pop_Sq（SqStack?&S）{
	if（S.top==S.base）{
		return?-1;
	}	
	return?*--S.top;
}
int?isEmpty（SqStack?S）{
	if（S.top==S.base）{
		return?false;
	}else?{
		return?true;
	}
}?
//判斷節(jié)點是否安全
int?isSafe（int?farmerint?wolfint?sheepint?cabbage）{
	if（（wolf==sheep&&farmer!=wolf）||（sheep==cabbage&&farmer!=sheep））{
		return?FALSE;
	}else?{
		return?TRUE;
	}
}?
//判斷節(jié)點是否有聯(lián)系
int?trueMove（MGraph?Gint?iint?j）{
	int?number=0;//農(nóng)夫帶過河的物品個數(shù)?
	if（G.vexs[i].farmer==G.vexs[j].farmer）{
		return??false;?//農(nóng)夫沒有移動?
	}
	if（G.vexs[i].cabbage!=G.vexs[j].cabbage）{
		number++;?
	}
	if（G.vexs[i].sheep!=G.vexs[j].sheep）{
		number++;
	}
	if（G.vexs[i].wolf!=G.vexs[j].wolf）{
		number++;
	}
	if（number>1）{
		return?false;
	}else{
		return?true;
	}
}?
//創(chuàng)建圖?
void?CreateUDG（MGraph?&G）{
	G.stanum=0;
	for（int?i=0;i<=1;i++）{
		for（int?j?=0;j<=1;j++）{
			for（int?k=0;k<=1;k++）{
				for（int?l=0;l<=1;l++）{
					if（isSafe（ijkl））{//判斷節(jié)點是否是安全的節(jié)點?
						G.vexs[G.stanum].farmer=i;?
						G.vexs[G.stanum].wolf=j;?
						G.vexs[G.stanum].sheep=k;?
						G.vexs[G.stanum].cabbage=l;?
						G.stanum++;
					}
				}
			}
		}
	}?
	for（int?i=0;i		for（int?j=0;j			if（trueMove（Gij））{
				G.arc[i][j]=TRUE;?
			}else?{
				G.arc[i][j]=INFINTITY;
			}
		}
	}?	
}?
//深度優(yōu)先遍歷
void?DFS（MGraph?GSqStack?&Sint?i）
{
	if（G.vexs[i].farmer==1&&G.vexs[i].wolf==1&&G.vexs[i].sheep==1&&G.vexs[i].cabbage==1）{
		k=0;
		while（isEmpty（S））{
			bay[sum][sums++]=Pop_Sq（S）;k++;
		}
		for（int?i=sums-1;i>=0;i--）{
			Push_Sq（Sbay[sum][i]）;
		}
		sum++;sums=0;
	}	
	for（int?j=0;j		if（G.arc[i][j]!=INFINTITY&&!visited[j]）{
			visited[j]=TRUE;//標記為訪問狀態(tài)
			Push_Sq（Sj）;
			DFS（GSj）;
			visited[j]=FALSE;
			Pop_Sq（S）;
		}
	}?
}
void?TraverseDFS（MGraph?GSqStack?&S）{
	for（int?i=0;i		visited[i]=FALSE;//初始化訪問前的狀態(tài)?
		ray[i]=-1;?
	}
	visited[0]=TRUE;
	Push_Sq（S0）;
	DFS（GS0）;
}
int?find（MGraph?Gint?m）
{
	for（int?i=0;

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????7114??2018-06-15?08:09??數(shù)據(jù)結(jié)構(gòu)農(nóng)夫過河.cpp

-----------?---------??----------?-----??----

?????????????????7114????????????????????1