hdu 1430 魔板 康托展开 + 很好的映射

http://acm.hdu.edu.cn/showproblem.php?pid=1430

如果从start ---> end，每一次都bfs进行，那么就肯定会超时。

考虑到先把start映射到原始状态"12345678"，然后又把end按照同样的规则，就是start的变化，映射到某一个地方。那么就可以看作是从固定的起点“12345678”-->newend，这个就可以打表了。

比如从87654321变化到12345678，那么就是8变成了1,7变成了2,6变成了3....。。那么end那里也按照这样变，在end中找一个8，变成1......以此类推。

相当于模仿start走动而已，肯定能走到的。

然后就可以打表。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>

class cantor {  //求1...n的排列的第k大 && hash排列，
public : ///class默认是private，所以要加上public
    int fac[12];
    cantor() { //预处理阶乘
        fac[0] = 1;
        for (int i = 1; i <= 11; ++i) {
            fac[i] = fac[i - 1] * i;
        }
    }
    int decode(char str[], int lenstr) { //O(n * n)的hash
        int ans = 0;
        for (int i = 1; i < lenstr; ++i) {
            int cnt = 0;
            for (int j = i + 1; j <= lenstr; ++j) {
                if (str[i] > str[j]) {
                    cnt++;
                }
            }
            ans += cnt * fac[lenstr - i];
        }
        return ans + 1;
    }
    vector<int> encode(int lenstr, int k) { //字典序排第k的是那个，k从1开始
        vector<int>ans;
        int toans;
        bool vis[12] = {0};
        for (int i = 1; i <= lenstr; ++i) {
            int t = k / fac[lenstr - i];
            k %= fac[lenstr - i];
            for (toans = 1; toans <= lenstr; ++toans) {
                if (vis[toans]) continue;
                if (t == 0) break;
                t--;
            }
            ans.push_back(toans);
            vis[toans] = true;
        }
        return ans;
    }
} cantor;
char be[23], en[23];
void A(char str[]) {
    for (int i = 1; i <= 4; ++i) {
        swap(str[i], str[9 - i]);
    }
}
void B(char str[]) {
    char t = str[4];
    for (int i = 4; i >= 2; --i) str[i] = str[i - 1];
    str[1] = t;
    t = str[5];
    for (int i = 5; i < 8; ++i) str[i] = str[i + 1];
    str[8] = t;
}
void C(char str[]) {
    char t1 = str[2];
    str[2] = str[7];
    char t2 = str[3];
    str[3] = t1;
    t1 = str[6];
    str[6] = t2;
    str[7] = t1;
}
struct node {
    char str[12];
    string now;
    node(char ss[]) {
        strcpy(str + 1, ss + 1);
    }
    node() {}
} que[40320 + 20];
bool vis[40320 + 20];
string ans[40320 + 20];
void bfs() {
    char st[55] = "q12345678";
    int fr, tail;
    fr = tail = 0;
    que[tail++] = node(st);
    que[fr].now = "";
    vis[cantor.decode(st, 8)] = true;
    while (fr < tail) {
        char t[22];
        strcpy(t + 1, que[fr].str + 1);
        A(t);
        int valt = cantor.decode(t, 8);
        if (vis[valt] == false) {
            vis[valt] = true;
            strcpy(que[tail].str + 1, t + 1);
            que[tail].now = que[fr].now + "A";
            ans[valt] = que[tail].now;
            tail++;
        }

        strcpy(t + 1, que[fr].str + 1);
        B(t);
        valt = cantor.decode(t, 8);
        if (vis[valt] == false) {
            vis[valt] = true;
            strcpy(que[tail].str + 1, t + 1);
            que[tail].now = que[fr].now + "B";
            ans[valt] = que[tail].now;
            tail++;
        }

        strcpy(t + 1, que[fr].str + 1);
        C(t);
        valt = cantor.decode(t, 8);
        if (vis[valt] == false) {
            vis[valt] = true;
            strcpy(que[tail].str + 1, t + 1);
            que[tail].now = que[fr].now + "C";
            ans[valt] = que[tail].now;
            tail++;
        }
        fr++;
    }
}
int pos[22], f[22];
char ten[22];
void work() {
    for (int i = 1; i <= 8; ++i) {
        pos[be[i] - '0'] = i;
    }
    for (int i = 1; i <= 8; ++i) {
        en[i] = pos[en[i] - '0'] + '0';
    }
//    cout << en + 1 << endl;
    cout << ans[cantor.decode(en, 8)] << endl;
}
int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
//    cout << cantor.decode("q87645321", 8) << endl;
    bfs();
    while (scanf("%s%s", be + 1, en + 1) != EOF) work();
    return 0;
}