AOJ1228 Beehives

問題リンク Beehives

• 概要

2人の人物がハチの巣の中を調査する。2人はセルを移動した方向を'a'〜'f'で表す。方向'a'〜'f'は反時計回りの順でつけるということは統一されているが、'a'の向きがどこを向いているかは統一されていない。2人の人物が調査した軌跡の文字列SとTが与えられる。文字列から、2人が調査したセルが全く同じかどうか判定せよ。2人とも、調査中に同じセルに対して2度以上訪問するということはしていない。調査したセルを裏返して一致するような場合は一致するとは見なさなくてよい。
0 <= |S|, |T| <= 100

• 解法

1人目が調査したセルの座標の集合を調べます。
2人目の軌跡がこのセルの座標の集合を全てカバーするか調べるために、開始点全通り、'a'の方向6通り、を全て組み合わせて試します。一致するケースがあればtrueでなければfalseです。

• ソース

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

//Beehives
public class AOJ1228 {

	int[][] d = {{0,1},{-1,0},{-1,-1},{0,-1},{1,0},{1,1}};
	
	void run(){
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt(), M = 150;
		sc.nextLine();
		while(T--!=0){
			char[] s = sc.nextLine().toCharArray(), t = sc.nextLine().toCharArray();
			sc.nextLine();
			Set<Integer> set = new HashSet<Integer>();
			int x = 100, y = 100;
			set.add(x*M+y);
			for(char c:s){
				x+=d[c-'a'][0]; y+=d[c-'a'][1];
				set.add(x*M+y);
			}
			boolean res = false;
			if(s.length==t.length){
				for(int S:set){
					if(res)break;
					for(int k=0;k<6;k++){
						x = S/M; y = S%M;
						int cnt = 1;
						for(char c:t){
							x+=d[(c-'a'+k)%6][0]; y+=d[(c-'a'+k)%6][1];
							if(!set.contains(x*M+y))break;
							cnt++;
						}
						if(cnt==set.size()){
							res = true; break;
						}
					}
				}
			}
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1228().run();
	}
}