农夫和狼、羊、白菜程序doc..doc

#include#define VEX_NUM 10 /最大顶点数typedef enumFALSE,TRUEBoolean;typedef struct /定义图的顶点数int Farmer,Wolf,Sheep,Veget;VexType;typedef structint vexnum,e; /图的当前顶点数和边数VexType vexsVEX_NUM;/顶点向量int adjVEX_NUMVEX_NUM;/邻接矩阵AdjGraph;Boolean visitedVEX_NUM;int pathVEX_NUM;int locate(AdjGraph *G,int F,int W,int S,int V)/查找顶点(F,W,S,V)在顶点向量中的位置int i;for(i=0;ivexnum;i+)if(G-vexsi.Farmer=F&G-vexsi.Wolf=W&G-vexsi.Sheep=S&G-vexsi.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;elsereturn 1;int is_connected(AdjGraph *G,int i,int j)/查找第i个状态之间是否可转换int k=0;if(G-vexsi.Wolf!=G-vexsj.Wolf) k+;if(G-vexsi.Sheep!=G-vexsj.Sheep) k+;if(G-vexsi.Veget!=G-vexsj.Veget) k+;if(G-vexsi.Farmer!=G-vexsj.Farmer&k=1)return 1;elsereturn 0;void CreatG(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;Vvexsi.Farmer=F;G-vexsi.Wolf=W;G-vexsi.Sheep=S;G-vexsi.Veget=V;i+;G-vexnum=i;for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)if(is_connected(G,i,j)G-adjij=G-adjji=1;elseG-adjij=G-adjji=0;return;void print_path(AdjGraph *G,int u,int v)/输出从u到v的简单路径int k;k=u;while(k!=v)coutvexsk.Farmervexsk.Wolfvexsk.Sheepvexsk.Vegetendl;k=pathk;coutvexsk.Farmervexsk.Wolfvexsk.Sheepvexsk.Vegetendl;void DFS_path(AdjGraph *G,int u,int v)/求出从u到v的简单路径int j;visitedu=TRUE;for(j=0;jvexnum;j+)if(G-adjuj&!visitedj&!visitedv)pathu=j;DFS_path(G,j,v);/主函数void main()int i,j;AdjGraph graph;CreatG(&graph);for(i=0;igraph.vexnum;i+)visitedi=FALSE;i=locate(&graph,0,0,0,0);j=locate(