AOJ1236 Map of Ninja House - nanikakaのAOJ航海日誌

概要

忍者屋敷を探検した結果が与えられる。忍者屋敷の構造を答えよ。
忍者屋敷は部屋と、部屋を結ぶドアからなる。
最初どこかの部屋にいる。その部屋のまだ開けていないドアを1つ開け、その先が未訪問の部屋ならば入室する。訪問したことがある部屋ならば部屋には入らない。その部屋の全てのドアを開けたら、この部屋に最初に入ってきたドアから出て戻る。このとき、カウンターという値を自分は覚えており、これは屋敷の最初の部屋からの距離を表す。
屋敷の探検記録は、ドアを開けたときにいつも記録される。
ドアの先が未訪問の場合、その部屋にあるドアの総数が1つ記録される。
訪問済みの場合、その部屋のカウンターと今いるカウンターとの差が負の整数として記録される。
屋敷の部屋数 < 100
1つの部屋のドアの最大数 < 40

解法

訪問記録を辿る際に、
今どこの部屋にいるか
各部屋の未オープンのドア数
訪問した部屋順のスタック
を覚えておけば大丈夫です。
まず、入口からの距離がカウンターの値なので、それはつまりその部屋が積まれているスタックの高さからカウンター値がわかります。
ex) スタックの下から3番目に部屋Xが積まれていた場合、部屋Xは最初の部屋から2回の移動を経てやってきてるのでカウンター値は3-1で2と分かります。
記録で負の数 x が来た場合、stack.get( stack.size () - 1 + x)によって、返される部屋が今訪問しようとしている訪問済みの部屋となります。
正の数が来た場合、次の部屋に進み、その部屋をスタックに積みます。
今いる部屋のドアを全て開けたら、スタックを辿り、ドアが残っている部屋までさかのぼります。
これを繰り返します。

ソース

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

//Map of Ninja House
public class AOJ1236 {

	class R{
		int id, door;
		List<Integer> adj;
		public R(int id, int door) {
			this.id = id;
			this.door = door;
			adj = new ArrayList<Integer>();
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while(T--!=0){
			R room[] = new R[101];
			Stack<R> v = new Stack<R>();
			int ID = 1;
			int x = sc.nextInt();
			room[ID] = new R(ID, x);
			R now = room[ID];
			v.push(room[ID]);
			ID++;
			for(;;){
				x = sc.nextInt();
				if(x==0)break;
				while(v.peek().door==0)v.pop();
				now = v.peek();
				if(x>0){
					R next = new R(ID, x);
					now.adj.add(ID); next.adj.add(now.id);
					next.door--;
					now.door--;
					room[ID] = next;
					v.push(next);
					now = next;
					ID++;
				}
				else{
					R r = v.get(v.size()-1+x);
					r.adj.add(now.id); now.adj.add(r.id);
					now.door--;
					r.door--;
				}
			}
			for(int i=1;i<ID;i++){
				System.out.print(i+" ");
				Collections.sort(room[i].adj);
				for(int j=0;j<room[i].adj.size();j++)System.out.print(room[i].adj.get(j)+(j==room[i].adj.size()-1?"\n":" "));
			}
		}
	}
	
	public static void main(String[] args) {
		new AOJ1236().run();
	}
}