#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int cost[] = {1, 2, 5, 10};
const char name[] = {'A', 'B', 'C', 'D'};
void back_a_bridge(vector<int>, vector<int>, int, string);
void copy_vector(vector<int>, vector<int>);
void copy_vector(vector<int>d, vector<int>s){
for(int i = 0; i < s.size(); i++)
d[i] = s[i];
}
/*
* member = 残っている人、member2 = 渡った人、total = それまでに掛かった時間
* cross_a_bridge() 二人渡す(memberを二人減らしmember2を増やす)
* back_a_bridge() 一人戻す(member2を一人減らしmemberを増やす)
*/
void cross_a_bridge(vector<int>member, vector<int>member2, int total, string s){
string ss = s;
ss += "→";
int a, b;
if(member.size() == 2){
a = member[0]; b = member[1];
if (name[a] > name[b]){
ss += name[b]; ss += name[a];
}else{
ss += name[a]; ss += name[b];
}
if(cost[a] > cost[b])
total += cost[a];
else
total += cost[b];
cout << ss << " cost:" << total << endl;
return;
}
int value1, value2, cost1, cost2;
int pos = member.size(), pos2 = member2.size();
vector<int>ls(member); vector<int>ls2(member2);
copy_vector(ls, member); copy_vector(ls2, member2);
for(int i = 0; i < pos - 1; i++){
value1 = ls[i];
cost1 = cost[value1];
ls.erase(ls.begin() + i); //memberの先頭削除
ls2.push_back(value1); //member2の末尾に足す
for(int j = 0; j < pos - 1; j++){
value2 = ls[i];
cost2 = cost[value2];
ls.erase(ls.begin() + i); //memberの先頭(+1)削除
ls2.push_back(value2); //member2の末尾(+1)に足す
string ss = s;
ss += "→";
if (name[value1] > name[value2]){
ss += name[value2]; ss += name[value1];
}else{
ss += name[value1]; ss += name[value2];
}
if(cost1 > cost2)
cost2 = cost1;
back_a_bridge(ls, ls2, total + cost2, ss);
ls2.erase(ls2.begin() + pos2 + 1);//member2の末尾(+2)削除
ls.push_back(value2); //memberの末尾(-1)に足す
}
ls2.erase(ls2.begin() + pos2); //member2の末尾(+1)削除
ls.push_back(value1); //memberの末尾に足す
}
}
void back_a_bridge(vector<int>member, vector<int>member2, int total, string s){
vector<int>ls(member); vector<int>ls2(member2);
copy_vector(ls, member); copy_vector(ls2, member2);
int value, cost1, pos = member.size(), n = member2.size();
for(int i = 0 ; i < n; i++){
value = ls2[0];
cost1 = cost[value];
ls2.erase(ls2.begin()); //member2の先頭を削除
ls.push_back(value); //memberの末尾に足す
string ss = s;
ss += "←(";
ss += + name[value];
ss += + ")";
cross_a_bridge(ls, ls2, total + cost1, ss);
ls.erase(ls.begin() + pos); //memberの末尾(+1)を削除
ls2.push_back(value); //member2の末尾に元先頭を戻す
}
}
int main(int argc, char** argv) {
vector<int> member = {0, 1, 2, 3};
vector<int> member2 = {};
string s = "";
try {
cross_a_bridge(member, member2, 0, s);
} catch(exception& e){
cout << e.what() << endl;
} catch(...){
cout << "何かの例外" << endl;
}
return 0;
}