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

AOJ 0171 Dice Puzzle

問題文: Dice Puzzle | Aizu Online Judge

やっぱりこういう問題時間食うなぁ。

ソースからは除いたけど、最初回転ライブラリを書いていた。24通り列挙して埋め込めたから削除。

バックトラック。枝狩は特別なものはしていない。

全通りの回転状態24コについての僕のイメージ

6 * 4 * 2 / 2 (対称なものをのぞくため/2)

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

// 0:TOP 1:FRONT 2:RIGHT 3:LEFT 4:BACK 5:BOTTOM 
string list[24] = {
	"012345","024135","031425","043215","103254","120534",
	"135024","152304","201453","215043","240513","254103",
	"304152","310542","345012","351402","402351","425031",
	"430521","453201","513240","521430","534120","542310"
};

bool used[8];
string data[8];
char puzzle[6][8];

// 各場所についてバックトラックする際に矛盾が生じないよう確認するべきところ。
// 偶数:number , 奇数:face に対応している変なフォーマット。終わりは-1。
int connect[8][8] = {
	{-1},
	{0,3,-1},
	{1,1,-1},
	{0,1,2,2,-1},
	{0,5,-1},
	{1,5,4,3,-1},
	{2,5,5,1,-1},
	{3,5,4,1,6,2,-1}
};

bool ok(char a,char b){
	return a != b && (a&~32) == (b&~32);
}

bool backTrack(int cur){
	if(cur == 8) return true;
	
	for(int d = 0 ; d < 8 ; d++){
		if(used[d]) continue;
		
		used[d] = true;
		for(int i = 0 ; i < 24 ; i++){
		
			for(int j = 0 ; j < 6 ; j++) puzzle[cur][j] = data[d][list[i][j]];
			
			bool f = true;
			for(int j = 0 ; connect[cur][j] != -1 ; j += 2){
				int pos  = connect[cur][j];
				int face = connect[cur][j+1];
				f &= ok(puzzle[pos][5-face] , puzzle[cur][face]);
			}
			if(f)if(backTrack(cur+1))return true;
		}
		used[d] = false;
	}

	return false;
}
int main(){
	for(int i = 0 ; i < 24 ; i++) for(int j = 0 ; j < 6 ; j++) list[i][j] -= '0';

	while(cin >> data[0] , data[0] != "0"){
		for(int i = 1 ; i < 8 ; i++) cin >> data[i];
		memset(used,0,sizeof(used));
		cout << (backTrack(0)?"YES":"NO") << endl;
	}
}