7-1 农夫过河-广度策略 (100 分)
一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。遗憾的是他只有一只小船，小船只能容下他和一件物品。这里只能是农夫来撑船。同时因为狼吃羊，而羊吃白菜，所以农夫不能留下羊和狼或者羊和白菜单独在河的一边，自己离开。好在狼属于肉食动物，不吃白菜。农夫怎样才能把所有的东西安全运过河呢？ 为了表示每个物品的位置，采用二进制位来区分南岸和北岸，0表示在南岸，1表示在北岸。用四个二进制位XXXX分别表示农夫、狼、菜和羊四个物品所在的位置。例如1110表示农夫、狼和菜在北岸，菜在南岸。农夫过河问题的初始状态为0000，结束状态为1111。
一.基本思路：
1.初始状态0000入队
2.当队列不空且没有到达结束状态1111时循坏以下操作：
①队头状态出队
②按照农夫一个人走、农夫分别带上三个走循坏以下操作：
~如果农夫和他们在同一岸，则计算新的状态。
~如果新状态是安全的并且是没有处理过的，则更新status[],并将新状态入队。
③当状态为1111时逆向输出status[]数组。
二.需要注意的时状态能否入队，要判断以下3条，满足一条件均不能入队。
①不可能：通过判断是否在统一对岸。
②不安全：通过安全函数判断。
③处理过：记录处理过的状态。
代码及注释如下
#include <stdio.h>
#include <stdlib.h>
typedef char DataType;
struct Queue
{
int Max;
int f;
int r;
DataType *elem;
};
typedef struct Queue *SeqQueue;
SeqQueue SetNullQueue_seq(int m)
{
SeqQueue squeue;
squeue = (SeqQueue)malloc(sizeof(struct Queue));
if (squeue == NULL)
{
printf("Alloc failure\n");
return NULL;
}
squeue->elem = (int*)malloc(sizeof(DataType)*m);
if (squeue->elem != NULL)
{
squeue->Max = m;
squeue->f = 0;
squeue->r = 0;
return squeue;
}
}
int IsNullQueue_seq(SeqQueue squeue)
{
return (squeue->f == squeue->r);
}
void EnQueue_seq(SeqQueue squeue,DataType x)
{
if((squeue->r+1)%squeue->Max==squeue->f)
printf("It is FULL Queue!");
else
{
squeue->elem[squeue->r]=x;
squeue->r=(squeue->r+1)%squeue->Max;
}
}
void DeQueue_seq(SeqQueue squeue)
{
if(IsNullQueue_seq(squeue)==1)
printf("it is empty queue!");
else
{
squeue->f=(squeue->f+1)%(squeue->Max);
}
}
DataType FrontQueue_seq(SeqQueue squeue)
{
if(IsNullQueue_seq(squeue)==1)
{
printf("It is empty queue");
return 33;
}
else
{
return squeue->elem[squeue->f];
}
}
//***************************************
int FarmerOnRight(int status)//判断当前条件下农夫的位置
{
return(0!=(status&0x08));
}
int WorfOnRight(int status)//判断当前位置下狼的位置
{
return(0!=(status&0x04));
}
int CabbageOnRight(int status)//判断当前位置下白菜的位置
{
return(0!=(status&0x02));
}
int GoatOnRight(int status)//判断当前位置下羊是否在南岸
{
return(0!=(status&0x01));
}
int IsSafe(int status)//判断当前位置下羊是否安全
{
if((GoatOnRight(status)==CabbageOnRight(status))&&(GoatOnRight(status)!=FarmerOnRight(status)))
return 0;//羊吃白菜
if((GoatOnRight(status)==WorfOnRight(status))&&(GoatOnRight(status)!=FarmerOnRight(status)))
return 0;狼吃羊
return 1;//其他状态时安全的
}
void FarmerRiver()
{
int i,movers,nowstatus,newstatus;
int status[16];//用于记录已考虑的状态路径
SeqQueue moveTo;//用于记录可以安全到达的中间状态
moveTo=SetNullQueue_seq(20);//创建空队列
EnQueue_seq(moveTo,0x00);//初始状态时所有物品在南岸
for(i=0;i<16;i++)//数组status初始化位-1
status[i]=-1;
status[0]=0;
while(!IsNullQueue_seq(moveTo)&&(status[15]==-1))
//队列非空且没有到达结束状态
{
nowstatus=FrontQueue_seq(moveTo);//取队头状态为当前状态
DeQueue_seq(moveTo);
for(movers=1;movers<=8;movers<<=1)//遍历三个要移动的物品
//考虑各种物品移动
if((0!=(nowstatus&0x08))==(0!=(nowstatus&movers)))
//考虑农夫与移动的物品在同一侧
{
newstatus=nowstatus^(0x08|movers);//计算新状态
//如果新状态时安全的且之前没有出现过
if(IsSafe(newstatus)&&(status[newstatus]==-1))
{
status[newstatus]=nowstatus;//记录新状态
EnQueue_seq(moveTo,newstatus);//新状态入队
}
}
}
//输出经过的装态路径
if(status[15]!=-1)//到达最终状态
{
printf("the reverse path is:\n");
for(nowstatus=15;nowstatus>=0;nowstatus=status[nowstatus])
{
printf("The nowstatus is:%d\n",nowstatus);
if(nowstatus==0)
return;
}
}
else
printf("No solution.\n");//问题无解
}
int main()
{
FarmerRiver();
return 0;
}