黑夜過橋 C++ 解題

    請幫助一家五口在黑夜中過河。

    注意事項：

    1.因為是黑夜，他們必須帶備燈。
    2.每位家庭成員都有不同的速度過橋，由1秒、3秒、6秒、8秒、到12秒。
    3.橋只可最多承受2人的重量。
    4.當2人同時在橋上行走，速度必跟隨較慢的一位。
    5.燈只足夠維持30秒。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int TARGET_STATE = 64-1;  //  111 111b

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

void showPauseMsg();

enum{
 lamp=32,
 m12=16,
 m8=8,
 m6=4,
 m3=2,
 m1=1
};

int cross[] = {
 m12, m8, m6, m3, m1,
 m12|m8, m12|m6, m12|m3, m12|m1,
 m8|m6, m8|m3, m8|m1,
 m6|m3, m6|m1,
 m3|m1
};

int crossCost[]={
 12, 8, 6, 3, 1,
 12, 12, 12, 12,
 8,8,8,
 6,6,
 3
};

int crossUppIdx = (sizeof(cross)/ sizeof(int))-1;

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

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

//get a binary digit N of iNumber, N start from Right to Left
// Rightmost is 1
//return 0 or 1, Bit N at iNumber

int getBitN(int iNumber, int N){
 return (iNumber >> (N-1)) & 1;
}

int getLampState (int iState){ return getBitN(iState, 6);}

bool isSafe(vector<int> &takerSnapshot, int addCost){
 int sum =0;

 for(int j=0; j<takerSnapshot.size();j++){
  sum += crossCost[takerSnapshot[j]];
 }

 sum += addCost;

 if (sum >30){ return false;}

 return true;
}

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

 for(int j=0; j < crossSnapshot.size();j++){
  if (state == crossSnapshot[j]){
   isTried = true;
   break;
  }
 }
 return isTried;
}

void printTaker(int i){
 char* msg[] = {
  "12", "8", "6", "3", "1",
  "(12,8)", "(12,6)", "(12,3)", "(12,1)",
  "(8,6)", "(8,3)", "(8,1)",
  "(6,3)", "(6,1)",
  "(3,1)"
 };

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

string getTaker(int i){
 char* msg[] = {
  "12", "8", "6", "3", "1",
  "(12,8)", "(12,6)", "(12,3)", "(12,1)",
  "(8,6)", "(8,3)", "(8,1)",
  "(6,3)", "(6,1)",
  "(3,1)"
 };

 if(i >= 0 && i <= crossUppIdx) {
  return string(msg[i]);
 }

 return string("");
}

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

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

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

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

  if (j%2 == 0){
   cout << " <---" << endl;
  } else {
   cout << " --->"<< endl;
  }
 }
 //add a dummy blank line
 cout <<endl;
}

void printTotalMins(vector<int> &takerSnapshot){
 int totalMins = 0;

 for(int j=0; j < takerSnapshot.size();j++){
  totalMins += crossCost[takerSnapshot[j]];
 }

 cout << "total mins used = " << totalMins << 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

 //cout << "roll back ...." << endl << endl;
 //printEveryWordState(takerSnapshot);
 //printEveryBitState(crossSnapshot);

 crossSnapshot.pop_back();
 takerSnapshot.pop_back();
}

bool isMoverSameSideWithBoat(int currentState, int mover){
 bool rv = false;
 int lampState = getLampState(currentState);

 if(lampState==0)
 {
  if ((currentState & mover) == 0){ rv = true; }
 }
 else
 {
  if ((currentState & mover)== mover){ rv = true;  }
 }

 return rv;
}

void crossRiver(int state,
    vector<int> &crossSnapshot)
{
 if (state == TARGET_STATE){
  //printEveryBitState(crossSnapshot);
  printEveryWordState(takerSnapshot);
  printTotalMins(takerSnapshot);

  //stop recurive iteration
  showPauseMsg(); // if u want to print similarly answer, hide this code
  exit(0);  // if u want to print similarly answer, hide this code
  return;
 }

 //for every cross choice
 for(int i=0; i<=crossUppIdx; i++){
  int mover = cross[i];

  bool isMoverSameWithBoat = isMoverSameSideWithBoat(state, mover);

  // if mover object is not same side as boat
  if (!isMoverSameWithBoat){
   continue;
  }

  int nextCrossState = (state ^ mover) ^ lamp; // use bitwise^ to toggle the Bit i

  bool isSafed = isSafe(takerSnapshot, crossCost[i]);

  bool isNotTry = (!isTry(nextCrossState));

  if( isSafed && isNotTry ){
   //printState(nextCrossState);
   //printTaker(i);

   //int x = takerSnapshot.size();
   recordTriedState(nextCrossState, i, crossSnapshot);
   //recurive to call itself
   crossRiver(nextCrossState, crossSnapshot);

   RollbackRecordState(nextCrossState, crossSnapshot);
  }
 }
}

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

int main() {
 //save first snapshot
 crossSnapshot.push_back(0);

 crossRiver(0, crossSnapshot);

 //showPauseMsg();
 return 0;
}

The cross step is show as belowing.
1. (6,1) <---
2. 1 --->
3. (3,1) <---
4. 3 --->
5. (12,8) <---
6. 1 --->
7. (3,1) <---

total mins used = 29
Press any key to be continue

延伸閱讀：

其他人的文章，如果是 N個人一共只帶了一只手電筒等變形問題的版本
http://blog.csdn.net/wuzhekai1985/article/details/6846934

http://renren.it/a/bianchengyuyan/_NET/20111006/133147.html


黑夜過橋問題是可遞迴解的