tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

AOJ 0171: Dice Puzzle

問題文:
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0171

概要:書けや、ゴラァ

解法:書く。
現役時代にHuziwaraにとんでもないやるだけクソ問と言われてたのでやったが、意外と適切な実装をすると特に努力しなくても1000B切れる。

やったこと:
c1,c2,c3に当てはまる場所のパターン全部を手で列挙しておく(8パターンしかない)。
8箇所に立方体を入れていくとき、それぞれ24パターンのうちのどれかを入れる。このとき
上の段
0 1
2 3
下の段
4 5
6 7
と入れるようにして、bitで上手く今までおいた左とか上とかのとの重複を考える。
ここで、c1同士は上下で接する、c2は隣のc3と接するということだけを意識してあとは縦と横どっちの接し方がc2,c3となるかを上手く考える。

#include<stdio.h>
#include<algorithm>
using namespace std;
char str[10][8];
int r[8][3]={
{0,1,2},
{0,2,4},
{0,4,3},
{0,3,1},
{5,2,1},
{5,4,2},
{5,3,4},
{5,1,3}
};
int used[10];
int now[8];
int r1[8];
int r2[8];
int solve(int a){
	if(a==8)return 1;
	for(int i=0;i<8;i++){
		if(used[i])continue;
		used[i]=1;
		now[a]=i;
		for(int j=0;j<8;j++)for(int k=0;k<3;k++){
			r1[a]=j;r2[a]=k;
			int cn=__builtin_popcount(a)%2;
			if((a&1)&&(str[i][r[j][(k+1+!cn)%3]]^32)!=str[now[a-1]][r[r1[a-1]][(r2[a-1]+1+cn)%3]])continue;
			if((a&2)&&(str[i][r[j][(k+1+cn)%3]]^32)!=str[now[a-2]][r[r1[a-2]][(r2[a-2]+1+!cn)%3]])continue;
			if((a&4)&&(str[i][r[j][k%3]]^32)!=str[now[a-4]][r[r1[a-4]][(r2[a-4])%3]])continue;
			int val=solve(a+1);
			if(val)return 1;
		}
		used[i]=0;
	}
	return 0;
}
int main(){
	while(1){
		scanf("%s",str[0]);
		if(str[0][0]=='0')break;
		for(int i=1;i<8;i++)scanf("%s",str[i]);
		for(int i=0;i<8;i++)used[i]=0;
		int res=solve(0);
		if(res)printf("YES\n");
		else printf("NO\n");
	}
}

999B, 大して時間かからなかった。