狼羊草问题(1).doc

狼羊草问题(1).txt 心脏是一座有两间卧室的房子,一间住着痛苦,一间住着快乐。人不能笑得太响,否则会吵醒隔壁的痛苦。#include<> #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 Create