1083.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1083 on 2006-01-09 at 13:37:48 */ 
#include <cstdio>
#include <queue>
#include <map>
using namespace std;

const int MAX = 128;

bool space[MAX][MAX];
map<long long, int> point;

long long parse(int);
bool connect(int, int, int);

int main()
{
	int n, t;
	
	for(t = 1; scanf("%d", &n) != EOF && n != 0; t++) {
		point.clear();
		long long x = parse(n), y = parse(n);
		int pn = 0;
		point[x] = pn++, point[y] = pn++;
		memset(space, false, sizeof(space));
		while((x = parse(n)) != -1 && (y = parse(n)) != -1) {
			int ox, oy;
			if(point.count(x) == 0) ox = pn++, point[x] = ox;
			else ox = point.find(x)->second;
			if(point.count(y) == 0) oy = pn++, point[y] = oy;
			else oy = point.find(y)->second;
			space[ox][oy] = space[oy][ox] = true;
		}
		printf("Maze #%d ", t);
		if(connect(0, 1, pn)) printf("can be travelled\n");
		else printf("cannot be travelled\n");
	}
	
	return 0;
}

long long parse(int n)
{
	int i, a;
	long long r = 0;
	for(i = 0; i < n; i++) {
		scanf("%d", &a);
		if(a == -1) return -1;
		else r = 10 * r + a;
	}
	return r;
}
bool connect(int s, int t, int n)
{
	queue<int> queue;
	bool visit[MAX] = { false };
	queue.push(s); visit[s] = true;
	while(!queue.empty()) {
		int p = queue.front(), i; queue.pop();
		for(i = 0; i < n; i++) {
			if(space[p][i] && !visit[i]) {
				if(i == t) return true;
				else visit[i] = true, queue.push(i);
			}
		}
	}
	return false;
}