1118.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include<stdio.h>
#include<map>
#include<string>
using namespace std;
int n;
map<string,int>ma;
int he[1000000];
int findhead(int t)
{
	if(he[t]==t)return t;
	else
	{
		he[t]=findhead(he[t]);
		return he[t];
	}
}

int main()
{
	int n,i,j,k;
	int T=0;
	int p;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)break;
		T++;
		char s[15];
		char ss[15],st[15];
		ma.clear();
		int cnt=0;
		for(i=0;i<n;i++)
		{
			scanf("%d",&p);
			ss[i]=char(p+48);
		}
		ss[n]=0;
		for(i=0;i<n;i++)
		{
			scanf("%d",&p);
			st[i]=char(p+48);
		}
		st[n]=0;
		while(scanf("%d",&p))
		{
			int a1,a2;
			if(p==-1)break;
			s[0]=char(p+48);
			for(i=1;i<n;i++)
			{
				scanf("%d",&p);
				s[i]=char(p+48);
			}
			s[n]=0;
			if(ma.find(string(s))==ma.end())
			{
				ma[string(s)]=++cnt;
				a1=cnt;
				he[cnt]=cnt;
				
			}
			else
			{
				a1=ma[string(s)];
			}
			for(i=0;i<n;i++)
			{
				scanf("%d",&p);
				s[i]=char(p+48);
			}
			s[n]=0;
			if(ma.find(string(s))==ma.end())
			{
				ma[string(s)]=++cnt;
				a2=cnt;
				he[cnt]=cnt;
			}
			else
			{
				a2=ma[string(s)];
			}
			int h1,h2;
			h1=findhead(a1);
			h2=findhead(a2);
			if(h1!=h2)
			{
				he[h1]=h2;
			}
		}
		if(ma.find(string(ss))==ma.end() || ma.find(string(st))==ma.end())
		{
			printf("Maze #%d cannot be travelled\n",T);
		}
		else
		{
			int a1,a2;
			a1=ma[string(ss)];
			a2=ma[string(st)];
			int h2,h1;
			h1=findhead(a1);
			h2=findhead(a2);
			if(h1==h2)
				printf("Maze #%d can be travelled\n",T);
			else printf("Maze #%d cannot be travelled\n",T);
		}
	}
	return 0;
}