PKU 1522 N-Credible Mazes
http://poj.org/problem?id=1522
n次元の空間での迷路を考える。
最初にn次元で座標のスタート地点とゴール地点が与えられ、その後に、いくつかの移動可能経路が与えられる。
このとき、スタートからゴールまで移動可能経路のみを通じて移動できるかを判定しろというような問題。
入力の処理が面倒くさいような気がしましたが、n<=10のようなので、long longに変換し、ユニオンファインドでそれぞれのノードが連結しているかを判定することにしました。
適当なおおきさで十分通るようなので、入力は優しめな気がします。
int un[100]; int find(int x){ if(x==un[x])return x; return un[x]=find(un[x]); } int unit(int a,int b){ un[find(a)]=un[find(b)]=find(a); } main(){ int n; int ma=0; while(cin>>n,n){ ++ma; set<ll> app; map<ll,int> pton; bool ff=false; rep(i,100)un[i]=i; while(true){ ll a; cin>>a; if(a==-1)break; rep(i,n-1){ ll k; cin>>k; a=a*10+k; } ll b=0; rep(i,n){ ll k; cin>>k; b=b*10+k; } int ap,bp; if(pton.count(a))ap=pton[a]; else ap=SZ(app),app.insert(a),pton[a]=ap; if(pton.count(b))bp=pton[b]; else bp=SZ(app),app.insert(b),pton[b]=bp; if(ff)unit(ap,bp); ff=true; } cout<<"Maze #"<<ma<<' '<<(find(0)==find(1)?"can":"cannot")<<" be travelled"<<endl; } }