AOJ1116 Jigsaw Puzzles for Computers - nanikakaのAOJ航海日誌

概要

9個のジグソーパズルのピースが与えられる。これらを使って3*3のパズルを完成できるような置き方は何通りあるかを答えよ。
ピースにはW,R,G,Bとこれら小文字の計8文字のうち4つが書かれている。ピースを並べたとき、接する辺に書いてある文字が、同じアルファベットで且つ大文字と小文字なら並べることができる。
入力ピースについて、以下のことが保証されている。
全く同じピースが2つ以上存在しない
ピースを傾けると他のピースと一致するようなピースは存在しない
ピースを180度回転すると元のピースと一致するようなピースは存在しない

解法

親切な前提が保証されているので、ピースの並べ方の重複カウントなどを考える必要がありません。
3*3の並べ方を全探索します。
ピースは4通りの置き方があります。ピースのどの辺を上に使うかという変数を持たせておき、1つのピースにつき4つのクラスインスタンスを作っておきました。
また、アルファベットは大文字と小文字で絶対値が同じ正と負の数をそれぞれ割り振っておきました。並べることができるかの判定は数字の和が0になるかどうかで分かります。

ソース

import java.util.Scanner;

//Jigsaw Puzzles for Computers
public class AOJ1116 {

	int trans(char ch){
		return ch=='R'?1:
			ch=='r'?-1:
			ch=='G'?2:
			ch=='g'?-2:
			ch=='B'?3:
			ch=='b'?-3:
			ch=='W'?4:-4;	
	}
	
	class R{
		int a[], top;
		public R(int[] a, int top) {
			this.a = a;
			this.top = top;
		}
	}
	
	R[][] assign;
	boolean[] u;
	int c;
	R[][] piece;
	
	void dfs(int k){
		if(k==9){
			c++;return;
		}
		int i=k/3;
		int j=k%3;
		for(int use=0;use<9;use++){
			if(u[use])continue;
			for(int d=0;d<4;d++){
				R r = piece[use][d];
				if(i>0){
					R up = assign[i-1][j];
					if(r.a[r.top]+up.a[(up.top+2)%4]!=0)continue;
				}
				if(j>0){
					R left = assign[i][j-1];
					if(r.a[(r.top+3)%4]+left.a[(left.top+1)%4]!=0)continue;
				}
				u[use] = true;
				assign[i][j] = r;
				dfs(k+1);
				u[use] = false;
			}
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		while(N--!=0){
			piece = new R[9][4];
			for(int i=0;i<9;i++){
				char[] s = sc.next().toCharArray();
				int[] a = new int[4];
				for(int j=0;j<4;j++)a[j]=trans(s[j]);
				for(int j=0;j<4;j++)piece[i][j]=new R(a, j);
			}
			c = 0;
			u = new boolean[9];
			assign = new R[3][3];
			dfs(0);
			System.out.println(c);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1116().run();
	}
}