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

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

#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;
   }
}