/*********************************************** * 農夫過河問題（P64 隊列的應用） * 約定：用四位二進制數分別順序表示農夫、狼、白菜和羊的狀態 *   即：{dddd} <=> {Farmer, Wolf, Cabbage, Goat} 其中：d={0,1} * 說明：0表示在東岸 1表示在西岸，初始狀態為0000，終止狀態為1111************************************************/#include<stdio.h>#include<stdlib.h>#define MAXSIZE 16typedef int EntryType;typedef struct queue{  EntryType data[MAXSIZE];  int front,rear;    //front隊頭，rear隊尾}SeqQueue, * SeqQueuePtr;// 創建空隊列SeqQueuePtr create_sequeue(void){  SeqQueuePtr pque;  pque = (SeqQueuePtr)malloc(sizeof(SeqQueue));  if(pque){    pque->front = 0;    pque->rear = 0;  }  else{    printf("Error: malloc() failed, out of memory!/n");  }  return(pque);}int is_queEmpty(SeqQueuePtr pque){  return( pque->front == pque->rear );}int is_queFull(SeqQueuePtr pque){  return( (pque->rear+1)%MAXSIZE == pque->front);}// 入隊int enqueue(SeqQueuePtr pque, EntryType x){  if(is_queFull(pque)){    printf("Queue Overflow Error: trying to add an element onto a full queue/n");    return 1;  }  else{    pque->data[pque->rear] = x;    pque->rear = (pque->rear + 1) % MAXSIZE;    return 0;  }}// 隊首元素出隊（返回0表示出隊異常，出隊操作前隊列為空）int dequeue(SeqQueuePtr pque, EntryType * e){  if(is_queEmpty(pque)){    printf("Empty Queue./n");    return 0;  }  else{    *e = pque->data[pque->front];    pque->front = (pque->front + 1) % MAXSIZE;    return 1;  }}int is_farmer_crossed(int state){  return ((state & 0x08) != 0);}int is_wolf_crossed(int state){  return ((state & 0x04) != 0);}int is_cabbage_crossed(int state){  return ((state & 0x02) != 0);}int is_goat_crossed(int state){  return ((state & 0x01) != 0);}// 若狀態相容（安全）則返回1，否則返回0int is_safe(int state){  if((is_goat_crossed(state) == is_cabbage_crossed(state)) &&    (is_goat_crossed(state) != is_farmer_crossed(state))) // 羊菜同岸且農夫不在場    return(0);  if((is_goat_crossed(state) == is_wolf_crossed(state)) &&    (is_goat_crossed(state) != is_farmer_crossed(state))) // 狼羊同岸且農夫不在場    return(0);  return(1);}void river_crossing_problem(){  int route[16];      // 記錄已經考慮過的狀態  int state;        // 記錄當前時刻的狀態（狀態編號的二進制形式即狀態本身）  int aftercross;     // 記錄漁夫當前的選擇（渡河對象）會導致的結果狀態  int passenger;      // 臨時變量，用于表達農夫的選擇（對應二進制位為1表示選中該乘客）  int results[16]={0};   // 輸出結果  int counter, i;  SeqQueuePtr states_que; //  states_que = create_sequeue(); // 創建“狀態”隊列  enqueue(states_que,0x00);   // 初始狀態0000入隊  for(int i = 0; i < 16; i++){    route[i] = -1;  }  //route[0] = 0;  while(!is_queEmpty(states_que) && (route[15] == -1))  {    if( !dequeue(states_que, &state) ){      printf("Error: dequeue() - the queue is empty/n");    }    // 依次考慮農夫可能的選擇：攜帶羊、白菜和狼，以及農夫只身渡河    for( passenger = 1; passenger<= 8; passenger <<= 1 )    {      // 由于農夫總是在過河，隨農夫過河的也只能是與農夫同側的東西      if(((state & 0x08) != 0) == ((state & passenger) != 0)){        // 如果農夫與當前乘客在河岸的同一側        aftercross = state^( 0x08|passenger ); // 渡河后的情況        if(is_safe(aftercross) && (route[aftercross] == -1)){          // 如果渡河后狀態安全，則將其狀態入隊          route[aftercross] = state; // 將當前狀態的索引記錄到路徑數組中（下標索引為后續狀態值）          enqueue(states_que, aftercross);        }      }    }//end for()  }//end while()  // 輸出過河策略：0表示在東岸 1表示在西岸，初始狀態為0000，終止狀態為1111  if(route[15] != -1)  {    //printf("The reverse path is:/n");    counter = 0;    for(state = 15; state != 0; state = route[state]){      //printf("The state is: %d /n",state);      results[counter] = state;      counter++;      //if(state == 0) return;    }    for(i = 0; i< counter; i++){      state= results[i];      aftercross = results[i+1];      if(state & 0x08){        printf("農夫從東岸到西岸:");      }      else{        printf("農夫從西岸到東岸:");      }      switch(state^aftercross ){      case 12:        printf("把狼帶過河/n");        break;      case 10:        printf("把菜帶過河/n");        break;      case 9:        printf("把羊帶過河/n");        break;      default:        printf("什么也不帶/n");        break;      }    }  }  else{    printf("No solution for this problem./n");  }}int main(void){  river_crossing_problem();  system("pause");  return 0;}