読者です 読者をやめる 読者になる 読者になる

AOJ Problem 1116 Jigsaw Puzzles for Computers

404 Not Found

バックトラック。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

#define TOP 0
#define RIGHT 1
#define BOTTOM 2
#define LEFT 3

vector<string> puz(9);
vector<string> cur(9);
bool done[9];
int ret;

bool diff(char a,char b){
	if(a != b && tolower(a) == tolower(b))return true;
	return false;
}
bool check(int p){
	const int di[] = {3,-1,-3,1};
	const int target[] = {TOP,RIGHT,BOTTOM,LEFT};
	const int self[] = {BOTTOM,LEFT,TOP,RIGHT};

	rep(i,4){
		if( p%3==0 && i == 1)continue;
		if( p%3==2 && i == 3)continue;	

		int t = p+di[i];
		if(t<0 || t>=9 || cur[t]== "")continue;
		
		if(!diff(cur[t][target[i]],cur[p][self[i]]))return false;
	}
	return true;
}
void bt(int x){

	if( x == 9){
		ret++;
		return;
	}
	
	rep(i,9){
		if(done[i])continue;
		
		rep(loop,4){
			rotate(puz[i].begin(),puz[i].begin()+1,puz[i].end());
			cur[x] = puz[i];
			done[i] = true;
			if(check(x))bt(x+1);
			done[i] = false;
			cur[x] = "";
		}
	}
	return;
}


int main(){
	int n; cin >> n;
	while(n--){
		rep(i,9)cin >> puz[i];

		ret = 0 , bt(0);
		
		cout << ret << endl;
	}
}