NoneOJ1001 - 魔方 Cube

2017/10/06

非常好的一道置换群搜索的题,见识到了。

题目来源是 QBXT 的一次模拟赛,出题人是吴克文。

题目

给一个 二阶魔方 的局面和最大搜索步数 N ,求字典序最小的还原方案的转动次数。

一共给出了 18 种单位转法:顶面顺时针 90 度,顶面顺时针 180 度,顶面顺时针 270 度,底面 90 度…

考虑到正对的两个面的旋转有旋转不变性,所以说实际转动的置换数只有 9 种,而且只有 3 种置换需要打表,其他的可以通过置换乘法得到。

妙啊。

重要的是思想,嘻嘻。

代码

  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
131
132
133
134
135
136
137
138
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;

int N;

struct group {
    int C[25];
    
    group() {
        for(int i=1;i<=24;i++)
            C[i] = i;
    }
    
    group(const group &a) {
        memcpy(C, a.C, sizeof(C));
    }
    
    group(const int* sq) {
        for(int i=1;i<=24;i++)
            C[i] = sq[i];
    }
    
    friend group operator*(const group &a, const group &b) {
        group ret;
        
        for(int i=1;i<=24;i++)
            ret.C[i] = b.C[a.C[i]];
        
        return ret;
    }
    
    bool check() {
        for(int i=1;i<=24;i+=4) {
            if(C[i] != C[i+1] || C[i] != C[i+2] || C[i] != C[i+3])
                return false;
        }
        return true;
    }
};

group op[10];

void init() {
    int *ptr = op[1].C;
    ptr[1] = 3;
    ptr[2] = 1;
    ptr[3] = 4;
    ptr[4] = 2;
    ptr[10] = 6;
    ptr[6] = 14;
    ptr[14] = 23;
    ptr[23] = 10;
    ptr[9] = 5;
    ptr[5] = 13;
    ptr[13] = 24;
    ptr[24] = 9;
    op[2] = op[1] * op[1];
    op[3] = op[1] * op[2];
    
    ptr = op[4].C;
    ptr[9] = 11;
    ptr[10] = 9;
    ptr[12] = 10;
    ptr[11] = 12;
    ptr[1] = 21;
    ptr[21] = 17;
    ptr[17] = 5;
    ptr[5] = 1;
    ptr[3] = 23;
    ptr[23] = 19;
    ptr[19] = 7;
    ptr[7] = 3;
    op[5] = op[4] * op[4];
    op[6] = op[4] * op[5];
    
    ptr = op[7].C;
    ptr[5] = 7;
    ptr[6] = 5;
    ptr[8] = 6;
    ptr[7] = 8;
    ptr[4] = 10;
    ptr[10] = 17;
    ptr[17] = 15;
    ptr[15] = 4;
    ptr[3] = 12;
    ptr[12] = 18;
    ptr[18] = 13;
    ptr[13] = 3;
    op[8] = op[7] * op[7];
    op[9] = op[7] * op[8];
}

int cl[] = {0, 1, 1, 1, 2, 2, 2, 3, 3, 3};
group ss;

int history[47]; int hpos;
int dfs(group g, int cla, int cnt) {
    if((g*ss).check()) {
//      puts("!");
        return cnt;
    }
    if(cnt > N) return 0;
    
    int k;
    for(int i=1;i<=9;i++) {
        if(cl[i] != cla) {
            if((k = dfs(op[i] * g, cl[i], cnt+1))) {
                history[hpos++] = i;
                return k;
            }
        }
    }
    
    return 0;
}

int main() {
    freopen("cube.in", "r", stdin);
    freopen("cube.out", "w", stdout);
    
    init();
    scanf("%d", &N);
    
    group gg;
    for(int i=1;i<=24;i++) scanf("%d", &ss.C[i]);
    
    dfs(gg, 0, 1);
    
    for(int i=hpos-1;i>=0;i--) {
        printf("%d ", history[i]);
    }
    puts("");
}