test/Rubik.cpp at master · Linzertorte/test · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<iostream>
#include<stdio.h>
#include<vector>
#include<limits.h>
#include<string.h>
using namespace std;
char face[7][3][3];
struct Tup{
    int f,i,j;
    Tup(){}
    Tup(int _f,int _i,int _j):f(_f),i(_i),j(_j){}
};
Tup rot1[6][8]={
    {Tup(1,0,0),Tup(1,0,1),Tup(1,0,2),Tup(1,1,2),Tup(1,2,2),Tup(1,2,1),Tup(1,2,0),Tup(1,1,0)},
    {Tup(2,0,0),Tup(2,0,1),Tup(2,0,2),Tup(2,1,2),Tup(2,2,2),Tup(2,2,1),Tup(2,2,0),Tup(2,1,0)},
    {Tup(3,0,0),Tup(3,0,1),Tup(3,0,2),Tup(3,1,2),Tup(3,2,2),Tup(3,2,1),Tup(3,2,0),Tup(3,1,0)},
    {Tup(4,0,0),Tup(4,0,1),Tup(4,0,2),Tup(4,1,2),Tup(4,2,2),Tup(4,2,1),Tup(4,2,0),Tup(4,1,0)},
    {Tup(5,0,0),Tup(5,0,1),Tup(5,0,2),Tup(5,1,2),Tup(5,2,2),Tup(5,2,1),Tup(5,2,0),Tup(5,1,0)},
    {Tup(6,0,0),Tup(6,0,1),Tup(6,0,2),Tup(6,1,2),Tup(6,2,2),Tup(6,2,1),Tup(6,2,0),Tup(6,1,0)}
};
Tup rot2[6][12]={
    {Tup(5,0,0),Tup(5,1,0),Tup(5,2,0),Tup(2,0,0),Tup(2,1,0),Tup(2,2,0),Tup(6,0,0),Tup(6,1,0),Tup(6,2,0),Tup(4,2,2),Tup(4,1,2),Tup(4,0,2)},
    {Tup(5,2,0),Tup(5,2,1),Tup(5,2,2),Tup(3,0,0),Tup(3,1,0),Tup(3,2,0),Tup(6,0,2),Tup(6,0,1),Tup(6,0,0),Tup(1,2,2),Tup(1,1,2),Tup(1,0,2)},
    {Tup(5,2,2),Tup(5,1,2),Tup(5,0,2),Tup(4,0,0),Tup(4,1,0),Tup(4,2,0),Tup(6,2,2),Tup(6,1,2),Tup(6,0,2),Tup(2,2,2),Tup(2,1,2),Tup(2,0,2)},
    {Tup(5,0,2),Tup(5,0,1),Tup(5,0,0),Tup(1,0,0),Tup(1,1,0),Tup(1,2,0),Tup(6,2,0),Tup(6,2,1),Tup(6,2,2),Tup(3,2,2),Tup(3,1,2),Tup(3,0,2)},
    {Tup(4,0,2),Tup(4,0,1),Tup(4,0,0),Tup(3,0,2),Tup(3,0,1),Tup(3,0,0),Tup(2,0,2),Tup(2,0,1),Tup(2,0,0),Tup(1,0,2),Tup(1,0,1),Tup(1,0,0)},
    {Tup(2,2,0),Tup(2,2,1),Tup(2,2,2),Tup(3,2,0),Tup(3,2,1),Tup(3,2,2),Tup(4,2,0),Tup(4,2,1),Tup(4,2,2),Tup(1,2,0),Tup(1,2,1),Tup(1,2,2)}
};
char b1[8],b2[12];
void rotate(int x){
    bool lft;
    if(x<0) lft = true, x=-x;
    else lft = false;
    x--;
    for(int k=0;k<8;k++){
        int f = rot1[x][k].f;
        int i = rot1[x][k].i;
        int j = rot1[x][k].j;
        b1[k] = face[f][i][j];
    }
    for(int k=0;k<12;k++){
        int f = rot2[x][k].f;
        int i = rot2[x][k].i;
        int j = rot2[x][k].j;
        b2[k] = face[f][i][j];
    }
    if(lft){
        char a = b1[0],b=b1[1];
        char c;
        for(int i=2;i<8;i++)
            b1[i-2]=b1[i];
        b1[6]=a;
        b1[7]=b;
        a = b2[0],b=b2[1],c=b2[2];
        for(int i=3;i<12;i++)
            b2[i-3]=b2[i];
        b2[9] = a;
        b2[10]=b;
        b2[11] = c;

    }else{
        char a,b,c;
        a = b1[6],b=b1[7];
        for(int i=5;i>=0;i--)
            b1[i+2] = b1[i];
        b1[0] = a,b1[1] = b;
        a = b2[9],b=b2[10],c=b2[11];
        for(int i=8;i>=0;i--)
            b2[i+3] = b2[i];
        b2[0] = a, b2[1] = b, b2[2] = c;

    }

    for(int k=0;k<8;k++){
        int f =rot1[x][k].f;
        int i =rot1[x][k].i;
        int j =rot1[x][k].j;
        face[f][i][j] = b1[k];
    }
    for(int k=0;k<12;k++){
        int f =rot2[x][k].f;
        int i =rot2[x][k].i;
        int j =rot2[x][k].j;
        face[f][i][j]= b2[k];
    }

}
bool check(){
    for(int i=1;i<=6;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                if(face[i][j][k]!=face[i][0][0]) return false;
    return true;
}
int path[100];
bool dfs(int cur,int d){
    if(check()) return true;
    if(cur>=d) return false;
    for(int c=-1;c<=1;c+=2)
        for(int x=1;x<=6;x++){
            path[cur] = c*x;
            rotate(x*c);
            if(dfs(cur+1,d)) return true;
            rotate(-x*c);
        }
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                scanf(" %c",&face[5][i][j]);
        for(int i=0;i<3;i++){
            for(int k=1;k<=4;k++)
                for(int j=0;j<3;j++) scanf(" %c",&face[k][i][j]);
        }
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                scanf(" %c",&face[6][i][j]);
        int d = 0;
        while(!dfs(0,d)) d++;
        for(int i=0;i<d;i++)
            printf("%d ",path[i]);
        printf("0\n");
    }
    return 0;
}