【HDOJ】3459 Rubik 2×2×2

模拟+DFS。

 /* 3459 */

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #define MAXN    10

 #define MAXL    1005

 #define U0        map[0][2]

 #define U1        map[0][3]

 #define U2        map[1][3]

 #define U3        map[1][2]

 #define F0        map[2][2]

 #define F1        map[2][3]

 #define F2        map[3][3]

 #define F3        map[3][2]

 #define R0        map[2][4]

 #define R1        map[2][5]

 #define R2        map[3][5]

 #define R3        map[3][4]

 #define L0        map[2][0]

 #define L1        map[2][1]

 #define L2        map[3][1]

 #define L3        map[3][0]

 #define B0        map[2][6]

 #define B1        map[2][7]

 #define B2        map[3][7]

 #define B3        map[3][6]

 #define D0        map[4][2]

 #define D1        map[4][3]

 #define D2        map[5][3]

 #define D3        map[5][2]

 const int n = ;

 const int m = ;

 int deep;

 char map[MAXN][MAXN];

 char op[MAXL];

 bool isValid() {

     bool ret;

     ret =\

         (U0==U1 && U0==U2 && U0==U3) &&\

         (L0==L1 && L0==L2 && L0==L3) &&\

         (R0==R1 && R0==R2 && R0==R3) &&\

         (F0==F1 && F0==F2 && F0==F3) &&\

         (B0==B1 && B0==B2 && B0==B3) &&\

         (D0==D1 && D0==D2 && D0==D3) ;

     return ret;

 }

 void rotateX() {

     char ch, ch1, ch2;

     // handle right

     ch = R0;

     R0 = R1;

     R1 = R2;

     R2 = R3;

     R3 = ch;

     ch1 = F1;

     ch2 = F2;

     // up -> front

     F1 = U1;

     F2 = U2;

     // back -> up

     U1 = B3;

     U2 = B0;

     // down -> back

     B0 = D2;

     B3 = D1;

     // front -> down

     D1 = ch1;

     D2 = ch2;

 }

 void rotateY() {

     char ch, ch0, ch1;

     // handle up

     ch = U0;

     U0 = U1;

     U1 = U2;

     U2 = U3;

     U3 = ch;

     ch0 = F0;

     ch1 = F1;

     // left -> front

     F0 = L0;

     F1 = L1;

     // back -> left

     L0 = B0;

     L1 = B1;

     // right -> back

     B0 = R0;

     B1 = R1;

     // front -> right

     R0 = ch0;

     R1 = ch1;

 }

 void rotateZ() {

     char ch, ch2, ch3;

     // handle front

     ch = F0;

     F0 = F1;

     F1 = F2;

     F2 = F3;

     F3 = ch;

     ch2 = U2;

     ch3 = U3;

     // right -> up

     U3 = R0;

     U2 = R3;

     // down -> right

     R0 = D1;

     R3 = D0;

     // left -> down

     D0 = L1;

     D1 = L2;

     // up -> left

     L1 = ch2;

     L2 = ch3;

 }

 bool dfs(int d) {

     if (d == deep)

         return isValid();

     op[d] = 'X';

     rotateX();

     if (dfs(d+))

         return true;

     rotateX();

     rotateX();

     rotateX();

     op[d] = 'Y';

     rotateY();

     if (dfs(d+))

         return true;

     rotateY();

     rotateY();

     rotateY();

     op[d] = 'Z';

     rotateZ();

     if (dfs(d+))

         return true;

     rotateZ();

     rotateZ();

     rotateZ();

     return false;

 }

 int main() {

     int i, j, k;

     #ifndef ONLINE_JUDGE

         freopen("data.in", "r", stdin);

         freopen("data.out", "w", stdout);

     #endif

     while () {

         for (i=; i<n; ++i)

             scanf("%s", map[i]);

         if (map[][] == '.')

             break;

         deep = ;

         while () {

             if (dfs())

                 break;

             ++deep;

         }

         op[deep] = '\0';

         puts(op);

     }

     return ;

 }