ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 0171 Dice Puzzle

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


・概要
8個のサイコロが与えられて、それらを2x2x2の立方体で表すことができるかを判定させる問題です。

組み合わせ方には条件があり、各サイコロの向き合う面は同じアルファベットで一方が小文字、もう一方が大文字でなければなりません。


・解法
サイコロをほげほげさせる問題です。

最初に1つのサイコロに対する目の状態を先にすべて列挙します。(24通りあります!!)
そうすると全部で24^8通りあるので、あとは 全探索 + 枝刈り で解くことができます。

アルファベットの大文字判定は isupper()、 小文字判定には islower() を使うことができます。


ソースコード

#include<iostream>
#include<string>
#include<cctype>
#include<cstring>
using namespace std;

#define rep(i,n) for(int i = 0 ; i < (int)(n) ; i++)
#define f first
#define s second
#define mp make_pair
typedef pair<int, string>P;

//top, front, right, left, back, bottom;
string table[24] = {"012345","024135","043215","031426",
		    "103254","135024","152304","120534",
		    "201453","215043","254103","240513",
		    "304152","345012","351402","310542",
		    "402351","425031","453201","430521",
		    "513240","534120","542310","521430"};

P selectDice[8];
string face[8];
bool ok;
bool used[8];

bool check(int d1, int s1, int d2, int idx, int s2){
   char c1 = face[selectDice[d1].f][((int)selectDice[d1].s[s1]-'0')];
   char c2 = face[d2][((int)table[idx][s2]-'0')];
   if((isupper(c1) && isupper(c2)) || (islower(c1) && islower(c2)))return false;
   return (c1 - 32 == c2) || (c1 == c2 - 32);
} 

void dfs(int index){
   if(ok)return;
   
   if(index==8) ok = true;
   
   else{
      for(int i = 0 ; i < 8 ; i++){
	 if(used[i])continue;
	 used[i] = true;
	 for(int j = 0 ; j < 24 ; j++){
	    if(index==1 && !check(0, 2, i, j, 3))continue;
	    if(index==2 && !check(0, 1, i, j, 4))continue;
	    if(index==3 && (!check(1, 1, i, j, 4) || !check(2, 2, i, j, 3)))continue;
	    if(index==4 && !check(0, 5, i, j, 0))continue;
	    if(index==5 && (!check(1, 5, i, j, 0) || !check(4, 2, i, j, 3)))continue;
	    if(index==6 && (!check(2, 5, i, j, 0) || !check(4, 1, i, j, 4)))continue;
	    if(index==7 && (!check(3, 5, i, j, 0) || !check(5, 1, i, j, 4) || !check(6, 2, i, j, 3)))continue;
	    
	    selectDice[index] = mp(i, table[j]);
	    dfs(index+1);
	 }
	 used[i] = false;
      } 
   }
}

string solve(){
   ok = false;
   memset(used,false,sizeof(used));
   dfs(0);
   return ok ? "YES" : "NO";
}

int main(){
   while(cin >> face[0]){
      if(face[0]=="0")break;
      
      for(int i = 1 ; i < 8 ; i++) cin >> face[i];
	
      cout << solve() << endl;
   }
   return 0;
}