1201-Lattice Practices

問題概要

問題文の図のように噛み合うような配置の個数を求めよ．
ただし，回転・反転は同じものと見なす．

解法

下の部分のみを全部定めて探索する．
回転・反転も数えるので最後に結果を8で割る．

実装(C++)

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

typedef long long int lli;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define rep(i,s,x) for(int i=s;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
char in[10][6];
char rev[10][6];
bool rev_equal[10];
bool input(){
	for(int i=0;i<10;i++){
		cin>>in[i];
		if(in[i][0]=='E')return false;
		REP(j,5){
			rev[i][4-j]=in[i][j];
		}
		rev_equal[i]=true;
		REP(j,5){
			if(rev[i][j]!=in[i][j]){
				rev_equal[i]=false;
				break;
			}
		}
	}
	return true;
}
char MAP[5][5];
void show(){
	REP(j,5){
		REP(i,5){
			cout<<MAP[i][j];
		}
		cout<<endl;
	}
	cout<<endl;
}
bool used[10];
int dfs(int k){
	int res=0;
	if(k==5){
		REP(i,10){
			if(!used[i]){
				bool ok=false;
				REP(j,5){
					bool pok=true;
					REP(l,5){
						if(MAP[l][j]==in[i][l]){
							pok=false;break;
						}
					}
					if(pok){
						ok=true;
						break;
					}
					pok=true;
					REP(l,5){
						if(MAP[l][j]==rev[i][l]){
							pok=false;break;
						}
					}
					if(pok){
						ok=true;
						break;
					}
				}
				if(!ok)return 0;
			}
		}
		return 1;
	}else{
		REP(i,10){
			if(!used[i]){
				used[i]=true;
				REP(j,5){
					MAP[k][j]=in[i][j];
				}
				res+=dfs(k+1);

				if(rev_equal[i]){
					used[i]=false;
					continue;
				}

				REP(j,5){
					MAP[k][j]=rev[i][j];
				}
				res+=dfs(k+1);

				used[i]=false;
			}
		}
	}
	return res;
}
int main(){
	while(input()){
		cout<<dfs(0)/8<<endl;
	}
}