农夫_狼_羊_菜过河问题
1.在解决这个问题的时候,首先得解决他们的状态问题。在这里我使用0 1表示他们的状态(0代表在河右岸,1代表左岸)
2.然后吧可以存在的状态保存在一个二维数组里面(类似(0,1,1,1)是不允许的)
3.判断能否过河,即状态的转变能否完成(如(0,0,0,0)——>(0,1,0,0)是不允许的,因为这样 农夫把狼带过来,菜会被羊吃掉)
4.连接他们之间的关系,即连接边。
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
#define MAXVALUE 1000
#define YES 1
#define NO 0
/*DataType结构*/
typedef struct
{
int famer,wolf,sheep,vagetable;
}DataType;
/*图结构*/
typedef struct
{
DataType vex[MAXSIZE];/*顶点数据表*/
int edg[MAXSIZE][MAXSIZE];/*边*/
int numedg,numvex;/*边的条数,结点个数*/
}AdjGraph;
/*初始化图 n个结点*/
void Graph_Initiate(AdjGraph *G,int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
{
G->edg[i][j]=0;
}
else
{
G->edg[i][j]=MAXVALUE;
}
}
}
G->numedg=0;/*初始化边的条数为0*/
G->numvex=0;/*初始化结点个数为0*/
}
/*判断是否安全*/
bool Safe(int famer, int wolf, int sheep, int vagetable)
{
if(famer!=sheep&&(wolf==sheep||sheep==vagetable))
{
return false;
}
else
{
return true;
}
}
/*创建所有安全的结点*/
int Create_All_Safe_Vex(AdjGraph *G)
{
int famer,wolf,sheep,vagetable;
int i=0;
for(famer=0;famer<=1;famer++)
{
for(wolf=0;wolf<=1;wolf++)
{
for(vagetable=0;vagetable<=1;vagetable++)
{
for(sheep=0;sheep<=1;sheep++)
{
if(Safe(famer,wolf,sheep,vagetable)==true)
{
G->vex[i].famer=famer;
G->vex[i].sheep=sheep;
G->vex[i].vagetable=vagetable;
G->vex[i].wolf=wolf;
i++;
}
}
}
}
}
return i;/*返回安全结点个数 */
}
/*能否过河*/
int Through_River(AdjGraph *G,int i,int j)
{
int k;
if(G->vex[i].sheep!=G->vex[j].sheep)/*羊过河*/
{
k++;
}
if(G->vex[i].vagetable!=G->vex[j].vagetable)/*菜过河 */
{
k++;
}
if(G->vex[i].wolf!=G->vex[j].wolf)/*狼过河*/
{
k++;
}
/*农夫一次最多只能带一个过河(即k<=1) 且农夫要改变状态*/
if(G->vex[i].famer!=G->vex[j].famer&&k<=1)
{
return 1;/*若满足最多带一个 返回真 */
}
else
{
return 0;/*否则为假 */
}
}
/*创建边*/
void Create_Edg(AdjGraph *G)
{
int i,j,n;
n=Create_All_Safe_Vex(G);/*获得结点个数 并且生成安全结点*/
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(Through_River(G,i,j))//如果可以过河 生成边
{
G->edg[i][j]=YES;//生成边---成功
G->numedg++;//边数+1
}
else
{
G->edg[i][j]=NO;//生成边---失败
}
printf("",Through_River(G,i,j));
}
}
}
/*取第一个领接顶点*/
int GetFirstVex(AdjGraph *G, int v)
{
int col,n;
n=Create_All_Safe_Vex(G);//获取结点个数
if(v<0||v>n)
{
printf("参数v越界!\n");
return -1;
}
for(col=0;col<n;col++)
{
if(G->edg[v][col]==YES)
{
return col;
}
}
return -1;
}
/*取下一个领接顶点*/
int GetNextVex(AdjGraph *G, int v1,int v2)
{
int col,n;
n=Create_All_Safe_Vex(G);
if(v1<0||v2<0||v1>=n||v2>=n)
{
printf("参数越界!\n");
return -1;
}
for(col=v2+1;col<n;col++)
{
if(G->edg[v1][col]==YES)
{
return col;
}
}
return -1;
}
/*深度优先遍历 从star开始查找的结点下标,end为star的第一个领接顶点下标*/
void Depth_First_Search(AdjGraph *G,int v,int visited[])
{
int w;
printf("\t(%d , %d , %d , %d )\n",G->vex[v].famer,G->vex[v].wolf,G->vex[v].vagetable,G->vex[v].sheep);
visited[v]=1;
w=GetFirstVex(G,v);
while(w!=-1)
{
if(visited[w]!=1)
{
Depth_First_Search(G,w,visited);//递归调用
}
w=GetNextVex(G,v,w);
}
}
/*main函数*/
int main()
{
AdjGraph G;
int n;
int visited[MAXSIZE];
n=Create_All_Safe_Vex(&G);//创建安全结点,并且获得结点个数
Graph_Initiate(&G,n);//初始化n个结点的图
Create_Edg(&G);//创建边
printf("方法为:(1在河水对岸,0不在河水对岸)\n");
printf("\t(农夫,狼,菜,羊)\n");
Depth_First_Search(&G,0,visited);
return 1;
}
效果图:
希望可以帮助到各位。