[ create a new paste ] login | about

Link: http://codepad.org/yHIqX3kj    [ raw code | output | fork ]

C++, pasted on Jan 13:
#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;
}


Output:
1
2
3
4
5
6
cc1plus: warnings being treated as errors
In function 'void copy_vector(__gnu_debug_def::vector<int, std::allocator<int> >, __gnu_debug_def::vector<int, std::allocator<int> >)':
Line 12: warning: comparison between signed and unsigned integer expressions
In function 'int main(int, char**)':
Line 88: error: scalar object 'member' requires one element in initializer
compilation terminated due to -Wfatal-errors.


Create a new paste based on this one


Comments: