狼、羊、菜威力加強版問題 C++ 解題

題目：

Lulu has to transfer the cabbage, the goat, the wolf, the stick and the fire from one bank of the river to the other bank.
But there are only two seats available on his boat !

Furthermore, if the goat and the cabbage stay together on a bank as Lulu is leaving on his boat, the goat will eat the cabbage.
If the wolf and the goat stay together as Lulu is leaving, the wolf will eat the goat !
If the stick and the wolf stay together as Lulu is leaving, the stick will beat the wolf !
If the fire and the stick stay together as Lulu is leaving, the fire will burn the stick !

Click on the "items" to place them on the boat or on the bank. Click on the arrow to make the boat cross the river.

There are 2 levels in this game.

Good luck !

Play
http://jeux.lulu.pagesperso-orange.fr/html/anglais/loupChe/loupChe2.htm

#include <iostream>
#include <vector>
using namespace std;

const int TARGET_STATE = 63;  // 111 111b

vector<int> crossSnapshot;
vector<int> takerSnapshot;

void showPauseMsg();

enum{
  FARMER=32, // 100000 b
  WOLF=16, // 010000 b
  GOAT = 8, // 001000 b
  CABBAGE=4, // 000100 b
  FIRE = 2,  // 000010 b
  STICK = 1  // 000001 b
};


//toggle the bit N array
//at bankA = 0, at bankB = 1

int cross[] = {
 FARMER,
 FARMER | WOLF,
 FARMER | GOAT,
 FARMER | CABBAGE,
 FARMER | FIRE,
 FARMER | STICK,

 FARMER | WOLF | GOAT,
 FARMER | WOLF | CABBAGE,
 FARMER | WOLF | FIRE,
 FARMER | WOLF | STICK,

 FARMER | GOAT | CABBAGE,
 FARMER | GOAT | FIRE,
 FARMER | GOAT | STICK,

 FARMER | CABBAGE | FIRE,
 FARMER | CABBAGE | STICK,

 FARMER | FIRE | STICK
};

void printState(int iState){
 //print out Bit N, N start from 0

 int N=6;
 for(int i=N-1;i>=0;i--)
 {
  cout << ((iState >> i ) & 1);//show Bit 3
 }
 cout << endl;
}

int farmer(int iState){
 //get a Bit N of iState, N start from 0
 return ((iState >> 5 ) & 1);
}
int wolf(int iState){
 return ((iState >> 4 ) & 1);
}
int goat(int iState){
 return ((iState >> 3 ) & 1);
}
int cabbage(int iState){
 return ((iState >> 2 ) & 1);
}

int fire(int iState){
 return ((iState >> 1 ) & 1);
}

int stick(int iState){
 return ((iState >> 0 ) & 1);
}

bool isSafe(int state){
 if( goat(state) == wolf(state) &&
  goat(state) != farmer(state))
 {
  return false;
 }

 if( goat(state) == cabbage(state) &&
  goat(state)!=farmer(state))
 {
  return false;
 }

 if( stick(state) == wolf(state) &&
  stick(state) != farmer(state))
 {
  return false;
 }

 if( fire(state) == stick(state) &&
  fire(state) != farmer(state))
 {
  return false;
 }

 return true;
}

bool isTry(int state){
 bool isTried = false;

 for(int j=0; j < crossSnapshot.size();j++){
  //printState(crossSnapshot[j]);

  if (state == crossSnapshot[j]){
   isTried = true;
   break;
  }
 }
 return isTried;
}

void printTaker(int i){
 char* msg[] = {
  "farmer goes alone",
  "farmer takes wolf",
  "farmer takes goat",
  "farmer takes cabbage",
  "farmer takes fire",
  "farmer takes stick",

  "farmer takes wolf & goat",
  "farmer takes wolf & cabbage",
  "farmer takes wolf & fire",
  "farmer takes wolf & stick",

  "farmer takes goat & cabbage",
  "farmer takes goat & fire",
  "farmer takes goat & stick",

  "farmer takes cabbage & fire",
  "farmer takes cabbage & stick",

  "farmer takes fire & stick"
 };

 if(i >= 0 && i <= 15) {
  cout << msg[i] << endl;;
 }
}

void printEveryState(vector<int> &crossSnapshot){
 cout << "total number cross state = " << crossSnapshot.size()<<endl;

 for(int j=0; j < crossSnapshot.size();j++){
  printState(crossSnapshot[j]);
 }
}

void printEveryState2(vector<int> &takerSnapshot){
 cout << "The cross step is show as belowing." << endl;

 for(int j=0; j < takerSnapshot.size();j++){
  cout << j+1 << ". ";
  printTaker(takerSnapshot[j]);
 }

 cout <<endl;
}

void recordTriedState(int state, int i, vector<int> &crossSnapshot){
 //save snapshot
 crossSnapshot.push_back(state);
 takerSnapshot.push_back(i);
}

void RollbackRecordState(int state, vector<int> &crossSnapshot){
 //delete previous snapshot
 crossSnapshot.pop_back();
 takerSnapshot.pop_back();
}

void crossRiver(int state, vector<int> &crossSnapshot){
 if (state == TARGET_STATE){
  //printEveryState(crossSnapshot);
  printEveryState2(takerSnapshot);
  //stop recurive iteration

  showPauseMsg();
  exit(0);
  return;
 }

 //for every cross choice
 for(int i=0; i< 15; i++){

  int boat = (crossSnapshot.size()+1) % 2; //0 or 1, 0 at banka, 1 at bankb
  int mover = cross[i];

  if(boat==0)
  {
   if ((state & mover)!= 0){ continue; }
  }
  else
  {
   if ((state & mover)!= mover){ continue; }
  }

  int nextCrossState = state ^ cross[i];

  if(isSafe(nextCrossState) && !isTry(nextCrossState)){
   recordTriedState(nextCrossState, i, crossSnapshot);

   //printTaker(i, state);
   //recurive to call itself
   crossRiver(nextCrossState, crossSnapshot);

   RollbackRecordState(nextCrossState, crossSnapshot);
  }
 }
}

void showPauseMsg(){
    cout << "Press any key to be continue" << endl;
 getchar();
}

int main() {
 int initialState = 0;

 //save first snapshot
 crossSnapshot.push_back(initialState);

 crossRiver(initialState, crossSnapshot);
 showPauseMsg();
 return 0;
}

Output:

The cross step is show as belowing.
1. farmer takes goat & stick
2. farmer goes alone
3. farmer takes wolf
4. farmer takes wolf & goat
5. farmer takes wolf & cabbage
6. farmer takes wolf
7. farmer takes goat
8. farmer takes goat & stick
9. farmer takes wolf & fire
10. farmer goes alone
11. farmer takes goat & stick

Press any key to be continue