# 数据结构-队列的应用-农夫过河问题

## Farmer across river

Posted by xuepro on November 10, 2017

## —农夫过河问题的队列实现—

/*农夫过河问题的广度优先算法*/

#include <stdio.h>

#include <malloc.h>

/*先实现农夫问题中需要的整数队列数据结构*/

#define OK  0

#define ERROR  1

typedef int EType;
typedef struct {
EType *data; // 动态分配存储空间
int capacity;
int front; // 头指针，若队列不空，指向队列头元素
int rear; // 尾指针，若队列不空，指向队列尾元素
} SqQueue;

int InitQueue(SqQueue *Q,int cap){
Q->data = (EType *)malloc(cap*sizeof(EType));
if(!Q->data )return ERROR;
Q->capacity = cap;
Q->front = 0;  Q->rear = 0;
}

int EnQueue(SqQueue *Q,EType e){
if((Q->rear+1)%Q->capacity==Q->front){  //队列满，扩容.你们去补充吧
return ERROR;
}
Q->data[Q->rear] = e;
Q->rear = (Q->rear+1)%Q->capacity;
return OK;
}

int DeQueue(SqQueue *Q){
if(Q->front==Q->rear) return ERROR;
Q->front = (Q->front+1)%Q->capacity;
return OK;
}

int GetFront(SqQueue Q,EType *e){
if(Q.front==Q.rear) return ERROR;
*e = Q.data[Q.front];
return OK;
}

int DestroyQueue(SqQueue *Q){
if(Q->data){
free(Q->data);
Q->data = 0;
}
return OK;
}

void ClearQueue(SqQueue *Q){
Q->front = 0;  Q->rear = 0;
}

int isQueueEmpty(SqQueue Q){
return Q.front==Q.rear ;
}

/*===农夫问题求解算法===*/
int safe(int location);
void traslate_path(int route[]);
int farmerProblem( ){
int movers, i,location,  newlocation;

int route[16];        /*记录已考虑的状态路径*/
for(i=0;i<16;i++)    route[i]=-1;

SqQueue   moveTo;
InitQueue(&moveTo,100);
EnQueue(&moveTo,0x00);
route[0]=0;

while(!isQueueEmpty(moveTo)&&(route[15]==-1)){
GetFront(moveTo,&location); /*得到现在的状态*/
DeQueue(&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(&moveTo,newlocation);
}
}
}
}

traslate_path(route);

if(route[15]!=-1){ /* 打印出路径 */
printf("逆向路径是 is : \n");
for(location=15;location>=0;location=route[location]){
printf("状态 is : %d\n",location);
if(location==0) return 1;
}
}
else   printf("无解.\n");

return 0;
}

int main(){
farmerProblem();
}

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)      /* 若状态安全则返回1*/
{
if((goat(location) == cabbage(location))
&&(goat(location)!=farmer(location)))
return (0);             /* 羊吃白菜*/
if((goat(location)==wolf(location))
&& (goat(location)!= farmer(location)))
return (0);             /* 狼吃羊*/
return (1);         /* 其他状态是安全的*/
}

/*-----translate--------*/

typedef struct lnode{
EType data;
struct lnode *next;
}LNode;

LNode *newNode(){
LNode *p = (LNode *)malloc(sizeof(LNode));
if(!p) return 0;
p->next = 0;
return p;
}

LNode* initLkStack(){
return newNode();
}

int pushLkStack(LNode *S,EType e){
LNode *p = newNode();
if(!p) return ERROR;
p->data = e;
p->next = S->next;
S->next = p;
return OK;
}

int popLkStack(LNode *S){
LNode *q = S->next;
if(!q) return ERROR;
S->next = q->next;
free(q);
return OK;
}

int topLkStack(LNode *S,EType *e){
if(!S->next) return ERROR;
*e = S->next->data;
return OK;
}

int isEmptyLkStack(LNode *S){
if(S->next ==0) return 1;
return 0;
}

void traslate(int pre_state,int cur_state){
int go = pre_state^cur_state;
printf("%d to %d\n ",pre_state,cur_state);

int famer_state = farmer(cur_state);
char north[] = "北岸",south[] = "南岸";

if( (0!=(go& 0x08))==(0!=(go & 0x01)) )
if(famer_state)
printf("农夫带羊到%s\n",north);
else  printf("农夫带羊%s\n",south);

else if( (0!=(go& 0x08))==(0!=(go & 0x02)) )
if(famer_state)
printf("农夫带白菜到%s\n",north);
else  printf("农夫带白菜%s\n",south);

else if( (0!=(go& 0x08))==(0!=(go & 0x04)) )
if(famer_state)
printf("农夫带狼到%s\n",north);
else  printf("农夫带狼%s\n",south);
else{
if(famer_state)
printf("农夫单独到%s\n",north);
else  printf("农夫单独%s\n",south);
}
}

void traslate_path(int route[]){
int pre_state = 0,cur_state,state;
LNode *S = initLkStack();
for(state=15;state>=0;state=route[state]){
/*printf("状态 is : %d\n",location);*/
if(state==0) break;
pushLkStack(S,state);
}

while(!isEmptyLkStack(S)){
topLkStack(S,&cur_state);
popLkStack(S);
traslate(pre_state, cur_state);
pre_state = cur_state;
}
}