一家六口過河問題 C++解題
出處不知，有多個變化身份的版本
版本1
一家庭欲過河.成員為:爸爸.媽媽.哥哥.姊姊.弟弟.妹妹.僕人.與一隻狗...
過河條件如下:
1.僅有一條小船可供渡河.每次最多搭乘2人(含駕駛)..且僅有爸爸.媽媽.僕人這3人會駕船..
2.爸爸不在兄弟身邊時.媽媽會打兄弟..
3.媽媽不在姊妹身邊時.爸爸會打姊妹..
4.僕人不在狗身邊時.狗會咬其他人..
請問這家人要如何平安過河?
版本2:
http://res.hkedcity.net/general/0001/51/31/riverIQGame.swf
全家人一起到郊外野餐，原本是歡樂的氣氛，卻碰到了逃獄的囚犯的襲擊，所幸逮捕他的警察也即時趕到，全家人因此暫時沒有危險了...；在警察一邊要保護全家人，一邊要看緊囚犯的路上，來到了一個需要過河的地方，但是只有一艘只能同時在兩人的小船，爸爸、媽媽、兩個兒子與兩個女兒，加上一名囚犯與一名警察這8個人該如何順利過河呢？
操作說明:
用滑鼠點選要乘船的人，在點選紅色拉桿，就可以過河。 注意，這家人有點...奇怪：
1.爸爸不可以在沒有媽媽的情況下跟女兒在一起，女兒會被責罵。
2.媽媽不可以在沒有爸爸的情況下跟兒子在一起，兒子會被修理。
3.囚犯不可以在沒有警察的情況下跟其他人在一起，囚犯會傷害他人。
這個版本被人用 flash 製造出來，有良好互動效果，所以就用這個題目做練習吧！
其他類似版本 iPad, iPhone
link
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int TARGET_STATE = 512-1; // 1 1111 1111b
vector<int> crossSnapshot;
vector<string> takerSnapshot;
void showPauseMsg();
enum{
Boat=256,
Father=128,
Mather=64,
Police=32,
Thief=16,
Boy1=8,
Boy2=4,
Girl1=2,
Girl2=1
};
int cross[] = {
Father,//0
Mather,
Police,
Father|Mather,
Father|Police,
Father|Boy1,
Father|Boy2,
Mather|Police,
Mather|Girl1,
Mather|Girl2,
Police|Thief,
Police|Boy1,
Police|Boy2,
Police|Girl1,
Police|Girl2
};
int crossUppIdx = 14;
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 getBoatState (int iState){ return getBitN(iState, 9);}
int father (int iState){ return getBitN(iState, 8);}
int mother (int iState){ return getBitN(iState, 7);}
int police (int iState){ return getBitN(iState, 6);}
int thief (int iState){ return getBitN(iState, 5);}
int boy1 (int iState){ return getBitN(iState, 4);}
int boy2(int iState){ return getBitN(iState, 3);}
int girl1(int iState){ return getBitN(iState, 2);}
int girl2(int iState){ return getBitN(iState, 1);}
bool isSafe(int state){
if( police(state) != thief(state)
&& (thief(state) == father(state) ||
thief(state) == mother(state) ||
thief(state) == boy1(state) ||
thief(state) == boy2(state) ||
thief(state) == girl1(state) ||
thief(state) == girl2(state))
)
{
return false;
}
if( father(state)!= mother(state) &&
(father(state) == girl1(state) ||
father(state) == girl2(state))
)
{
return false;
}
if( mother(state)!= father(state) &&
(mother(state) == boy1(state) ||
mother(state) == boy2(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[] = {
"father, _____",
"mother, _____",
"police, _____",
"father, mother",
"father, police",
"father, boy1",
"father, boy2",
"mother, police",
"mother, girl1",
"mother, girl2",
"police, thief",
"police, boy1",
"police, boy2",
"police, girl1",
"police, girl2"
};
if(i >= 0 && i <= crossUppIdx) {
cout << msg[i] << endl;
}
}
string getTaker(int i){
char* msg[] = {
"father, _____",
"mother, _____",
"police, _____",
"father, mother",
"father, police",
"father, boy1",
"father, boy2",
"mother, police",
"mother, girl1",
"mother, girl2",
"police, thief",
"police, boy1",
"police, boy2",
"police, girl1",
"police, girl2"
};
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<string> &takerSnapshot){
cout << "The cross step is show as belowing." << endl;
for(int j=0; j < takerSnapshot.size();j++){
cout << j+1 << ". ";
cout << takerSnapshot[j];
if (j%2 == 0){
cout << " --->" << endl;
} else {
cout << " <---"<< endl;
}
}
//add a dummy blank line
cout <<endl;
}
void recordTriedState(int state, int i, vector<int> &crossSnapshot){
//save snapshot
crossSnapshot.push_back(state);
takerSnapshot.push_back(getTaker(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 boat = getBoatState(currentState);
if(boat==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);
//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) ^ Boat; // use bitwise^ to toggle the Bit i
bool isSafed = isSafe(nextCrossState);
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() {
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. police, thief --->
2. police, _____ <---
3. police, boy1 --->
4. police, thief <---
5. father, boy2 --->
6. father, _____ <---
7. father, mother --->
8. mother, _____ <---
9. police, thief --->
10. father, _____ <---
11. father, mother --->
12. mother, _____ <---
13. mother, girl1 --->
14. police, thief <---
15. police, girl2 --->
16. police, _____ <---
17. police, thief --->
Press any key to be continue
-------------------------------------------------
DOS/capture screen output to a file
click the control menu button on a command window (you can find this button on the left upper corner). Or press Alt + space_bar.
Once the control menu opens, select Edit. From there you can Select All, Mark, or Copy the text you require from the command window.
This text is then copied to the standard Windows clipboard. From there you can paste it in another Windows program.
