#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "queue.h"
void main()
{
int i,movers,location,newlocation;
int route[16];//用于记录已考虑的状态路径
PSeqQueue moveTo;//用于记录可以安全到达的中间状态
moveTo=createEmptyQueue_seq();//创建空队列
enQueue_seq(moveTo,0x00);//初始状态进队列
for(i=0;i<16;i++)
route[i]=-1;//准备数组route初值
route[0]=0;
while(!isEmptyQueue_seq(moveTo)&&(route[15]==-1))
{
location=frontQueue_seq(moveTo);//取对头状态为当前状态
deQueue_seq(moveTo);
for(movers=1;movers<=8;movers<<=1)//考虑各种物品移动
if((0!=(location&0x08))==(0!=(location&movers)))
{//农夫与移动的物品在统一岸
newlocation=location^(0x08|movers);//计算新状态
if(safe(newlocation)&&(route[newlocation]==-1))
{//新状态安全且未处理
route[newlocation]=location;//记录新状态的前驱
enQueue_seq(moveTo,newlocation);//新状态入队
}
}
}
//打印出路径
if(route[15]!=-1) //到达最终状态
{
printf("The reverse path is:\n");
for(location=15;location>=0;location=route[location])
{
printf("The location is :%d\n",location);
if(location==0)
//exit(0);
break;
}
}
else
printf("No solution.\n"); //问题无解
system("pause>nul");//调用系统暂停命令
}
int farmer(int location)//判断农夫的位置
{return (0!=(location&0x08));}
int wolf(int location)//判断狼的位置
{return (0!=(location&0x04));}
int cabbage(int location)//判断白菜的位置
{return (0!=(location&0x02));}
int goat(int location)//判断羊的位置
{return (0!=(location&0x01));}
int safe(int location)
{//若状态安全则返回真
if((goat(location)==cabbage(location))&&(goat(location)!=farmer(location)))
return 0;//羊吃白菜
if((goat(location)==wolf(location))&&(goat(location)!=farmer(location)))
return 0;//狼吃羊
return 1;//其他状态是安全的
}
