USACO Wormholes(wormhole) 题解

这里再次强烈推荐USACO，因为他们每一题的题解现在有视频了！！

 

在这一题上花了一天时间，想到用recursion来解决问题，想到检测loop的方法，不过还是出了错误，loop解决方案参考了http://blog.csdn.net/thestoryofsnow/article/details/39821333

 

通过之后，看了USACO自己的题解，他们有更简洁和高效的解决方案，发现大家看问题的方式真的是不一样，这个人应该是那种大牛的赶脚，同时突然很庆幸自己在USACO上花时间，因为这一次比以往的任何一次学到的东西都多，包括对问题抽象化的方式也跟以前大不相同。

 

下面是我的代码，我比较喜欢用容器，因为不会越界，同时兼容大的数据。但是。。显然没有USACO题解给出的解决方案好：

 

/*
ID: bbsunch2
PROG: wormhole
LANG: C++
*/

//#include "stdafx.h"
#include <map>
#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

struct UNI_PAIR{
	int x;
	int y;
};

// given an enter index, find the corresponding out index
int get_exit_index(int enterIndex, vector<UNI_PAIR> chosen_pairs){
	for (int i = 0; i < chosen_pairs.size(); i++){
		UNI_PAIR p = chosen_pairs[i];
		if (enterIndex == p.x){
			//cout << p.x << "&" << p.y << endl;
			return p.y;
			
		}
		if (enterIndex == p.y){
			//cout << p.x << "&" << p.y << endl;
			return p.x;
		}
	}
	return -1;
}

// getting out of the exit index, find the next corresponding enter index
int get_enter_index(int beforeIndex, vector<UNI_PAIR> points, map<int, vector<int> > coordinate_y__x){
	UNI_PAIR beforePoint = points[beforeIndex];
	int before_y = beforePoint.y;
	int before_x = beforePoint.x;
	UNI_PAIR enterPoint;
	enterPoint.y = before_y;
	vector<int> xVector = coordinate_y__x[before_y];
	//bool found_enter = false;
	for (int i = 0; i < xVector.size(); i++){
		if (before_x == xVector[i]){
			if (i == xVector.size() - 1){
				return -1;
			}
			else{
				enterPoint.x = xVector[i + 1];
				break;
			}
		}
	}
	for (int i = 0; i < points.size(); i++){
		if (points[i].x == enterPoint.x && points[i].y == enterPoint.y){
			return i;
		}
	}
}

int add_path(int point, vector<int> & path){
	for (int i = 0; i < path.size(); i++){
		if (point == path[i]){
			path.push_back(point);
			return 0;
		}
	}
	path.push_back(point);
	return 1;
}

// for each combination and each entry, check if there is a loop exist
bool check_loop(vector<UNI_PAIR > points, map<int, vector<int> > coordinate_y__x, vector<UNI_PAIR> chosen_pairs){
	
	//for each entry, check if there is loop
	for (int i = 0; i < points.size(); i++){
		//int entryIndex = i;
		int enterIndex = i;
		int exitIndex = get_exit_index(enterIndex, chosen_pairs);
		vector<int> path;
		path.push_back(enterIndex);
		//path.push_back(exitIndex);
		bool is_loop = false;
		while (get_enter_index(exitIndex, points, coordinate_y__x) >= 0){
			enterIndex = get_enter_index(exitIndex, points, coordinate_y__x);
			exitIndex = get_exit_index(enterIndex, chosen_pairs);
			if (enterIndex == -1 || exitIndex == -1){
				cout << "Error in check_loop" << endl;
			}
			
			if (! add_path(enterIndex, path) ){
				//return true;
				is_loop = true;
				break;
			}
			//path.push_back(exitIndex);
		}
		/*for (int i = 0; i < path.size(); i++){
			cout << path[i];
			if (i != path.size() - 1){
				cout << "->";
			}
		}
		cout << endl;*/
		if (is_loop) return true;
	}
	
	return false;
}



vector<vector<UNI_PAIR> > generate_combinations(const vector<int> point_indexs){
	if (point_indexs.size() % 2 != 0){
		cout << "Error in generate_combinations, odd num: " << point_indexs.size() << endl;
	}
	if (point_indexs.size() == 2){
		UNI_PAIR singlePair;
		singlePair.x = point_indexs[0];
		singlePair.y = point_indexs[1];
		vector<UNI_PAIR> singleVector;
		singleVector.push_back(singlePair);
		vector<vector<UNI_PAIR> > singleCombination;
		singleCombination.push_back(singleVector);
		return singleCombination;
	}
	else{
		vector<vector<UNI_PAIR> > combinations;
		for (int i = 1; i < point_indexs.size(); i++){
			UNI_PAIR firstPair;
			
			vector<int> left_indexs;
			for (int j = 0; j < point_indexs.size(); j++){
				left_indexs.push_back(point_indexs[j]);
			}
			firstPair.x = left_indexs[0];
			firstPair.y = left_indexs[i];
			left_indexs.erase(left_indexs.begin() + i);
			left_indexs.erase(left_indexs.begin());
			vector<vector<UNI_PAIR> > left_combinations = generate_combinations(left_indexs);

			for (int k = 0; k < left_combinations.size(); k++){
				combinations.push_back(left_combinations[k]);
				int lastIndex = combinations.size() - 1;
				combinations[lastIndex].push_back(firstPair);
			}
		}
		return combinations;
	}
}

// test function generate_combinations
void output_combinations(vector<vector<UNI_PAIR> > combinations){
	//vector<int> point_indexs;
	//point_indexs.push_back(0);
	//point_indexs.push_back(1);
	//point_indexs.push_back(2);
	//point_indexs.push_back(3);

	//vector<vector<UNI_PAIR> > combinations = generate_combinations(point_indexs);

	for (int i = 0; i < combinations.size(); i++){
		cout << "combination " << i << ": ";
		for (int k = 0; k < combinations[i].size(); k++){
			cout << combinations[i][k].x << "-" << combinations[i][k].y << " ";
		}
		cout << endl;
	}
}

// given coordinates, count the number of combinations that will cause loop
int count_loops(vector<UNI_PAIR > points, map<int, vector<int> > coordinate_y__x){
	//iterate all combinations
	int loopCount = 0;
	vector<int> point_indexs;
	for (int i = 0; i < points.size(); i++){
		point_indexs.push_back(i);
		//cout << points[i].x << "-" << points[i].y << "\t";
	}
	//cout << endl;
	vector<vector<UNI_PAIR> > combinations = generate_combinations(point_indexs); //store index in points
	//output_combinations(combinations);
	// foreach combination, check if there is loop;
	for (int i = 0; i < combinations.size(); i++){
		vector<UNI_PAIR> chosen_pairs = combinations[i];
		bool is_loop = check_loop(points, coordinate_y__x, chosen_pairs);
		if (is_loop){
			loopCount ++;
		}

		/*cout << "combination " << i << ": ";
		for (int k = 0; k < combinations[i].size(); k++){
			cout << combinations[i][k].x << "-" << combinations[i][k].y << " ";
		}
		cout << ": " << is_loop;
		cout << endl;*/
	}
	return loopCount;
}



int main(int argc, char* argv[])
{
	ofstream fout("wormhole.out");
	ifstream fin("wormhole.in");

	int N = 0;
	fin >> N;

	map<int, vector<int> > coordinate_y__x; // key is y, value is all x coordinates using the same y
	vector<UNI_PAIR > points;
	map<int, int> testMap;

	for (int i = 0; i < N; i++){
		int x, y;
		fin >> x >> y;
		UNI_PAIR singlePoint;
		singlePoint.x = x;
		singlePoint.y = y;
		points.push_back(singlePoint);

		if (coordinate_y__x.find(y) == coordinate_y__x.end()){
			vector<int> tempVector;
			tempVector.push_back(x);
			coordinate_y__x.insert(pair<int, vector<int> >(y, tempVector));
		}
		else{
			coordinate_y__x[y].push_back(x);
		}
	}

	for (map<int, vector<int> >::iterator it = coordinate_y__x.begin(); it != coordinate_y__x.end(); it++){
		int y = it->first;
		sort(coordinate_y__x[y].begin(), coordinate_y__x[y].end());
		//for (int i = 0; i < coordinate_y__x[y].size(); i++){
		//	cout << y << coordinate_y__x[y][i] << endl;
		//}
	}

	int loopCount = count_loops(points, coordinate_y__x);
	//test_combinations();
	cout << loopCount << endl;
	fout << loopCount << endl;
	
	//stay
	//int i;
	//cin >> i;
	return 0;
}