问题描述
三名商人各带–个随从乘船渡河,一只小船只能容纳二人,由他们自己划行.随从们密约,在河的任一岸，一旦随从的人数比商人多,就杀人越货,商人们怎样才能安全渡河呢？
问题建模
考虑用深度优先搜索解决此问题，提前记录在船承载量为2时候，所有可行的移动状态，以及所有安全的商人和随从的数量情况，用变量同时在搜索的过程中记录答案，一旦找到左岸已经完全没有人的情况立刻结束搜索，输出方案
变量声明
Ans为记录步骤的数组
Move对于某次决策有哪些移动方法
Sav用于判断此时的状态是否安全
Boat 表示当前这一步船是过去还是回来
运行结果
图片解释
共11步
- 1 两个随从过去
- 2 一个随从回来
- 3 再两个随从过去
- 4 一个随从回来
- 5 两个商人过去
- 6 一个随从和一个商人回来
- 7 两个商人过去
- 8 一个随从回来
- 9 两个随从过去
- 10 一个随从回来
- 11 最后两个随从过去
Code
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int Move[5][2]= {{0, 2}, {1, 1}, {2, 0}, {0, 1}, {1, 0}};//对于某次决策有哪些移动方法 4 const bool Sav[4][4] = {{0, 0, 0, 0}, {1, 0, 1, 1}, {1, 1, 0, 1}, {0, 0, 0, 0}};//判断此时的状态是否安全 5 int Ans[1001][2], step = 1; 6 bool Boat[1001], flag; 7 bool rep (int a, int b, bool flag) {//repeat函数，判断是否有重复状态 8 for(int i = 0; i < step; i ++) { 9 if(a == Ans[i][0] && b == Ans[i][1] && Boat[i] == flag) return 1; 10 } 11 return 0; 12 } 13 bool UnSave (int Tr, int Co, int flag) { 14 if (Tr < 0||Tr > 3||Co < 0||Co > 3|| Sav[Tr][Co] || rep(Tr, Co, flag)) return 1; 15 return 0; 16 } 17 //判断是否不安全的函数 18 void dfs (int Trader, int Cortege) { //商人和随从 19 if(!Trader && !Cortege) { //如果找到了方案立刻输出 20 cout << step - 1 << endl; 21 cout << "（左岸商人" << "," << "左岸随从)" <<" " << "（右岸商人" << "," << "右岸随从)" << endl; 22 for (int i = 0;i < step; i++) { 23 cout << "(" << Ans[i][0] << "," << Ans[i][1] << ") "; 24 cout << "(" << 3 - Ans[i][0] << "," << 3 - Ans[i][1] << ")" << endl; 25 } 26 exit(0); //找到答案，直接退出搜索 27 } 28 else if (!flag) { 29 for (int i = 0; i <= 4; i ++) { 30 Trader -= Move[i][0], Cortege -= Move[i][1]; 31 if (UnSave(Trader, Cortege, flag)) { 32 Trader += Move[i][0], Cortege += Move[i][1]; 33 continue; 34 } 35 Ans[step][0] = Trader, Ans[step][1] = Cortege, Boat[step] = flag; 36 // 存储答案 37 step ++, flag = (!flag); 38 dfs (Trader, Cortege); 39 flag = (!flag); 40 Trader += Move[i][0]; 41 Cortege += Move[i][1];//回溯 42 step --; 43 } 44 } 45 //下面是划回去的状态，与上面同理 46 else { 47 for (int i = 0;i <= 4;i ++) { 48 Trader += Move[i][0]; 49 Cortege += Move[i][1]; 50 if (UnSave (Trader, Cortege, flag)) { 51 Trader -= Move[i][0], Cortege -= Move[i][1]; 52 continue; 53 } 54 Ans[step][0] = Trader, Ans[step][1] = Cortege, Boat[step] = flag; 55 step ++; 56 flag = (!flag); 57 dfs (Trader, Cortege); 58 flag = (!flag); 59 Trader -= Move[i][0]; 60 Cortege -= Move[i][1]; 61 step --; 62 } 63 } 64 } 65 int main() { 66 Ans[0][0] = Ans[0][1] = 3, Boat[0] = 1; 67 dfs (3, 3); 68 return 0; 69 }