魔板

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4242    Accepted Submission(s): 1011

Problem Description
在魔方风靡全球之后不久，Rubik先生发明了它的简化版——魔板。魔板由8个同样大小的方块组成，每个方块颜色均不相同，可用数字1-8分别表示。任一时刻魔板的状态可用方块的颜色序列表示：从魔板的左上角开始，按顺时针方向依次写下各方块的颜色代号，所得到的数字序列即可表示此时魔板的状态。例如，序列(1,2,3,4,5,6,7,8)表示魔板状态为：
1 2 3 4
8 7 6 5
对于魔板，可施加三种不同的操作，具体操作方法如下：
A: 上下两行互换,如上图可变换为状态87654321
B: 每行同时循环右移一格,如上图可变换为41236785
C: 中间4个方块顺时针旋转一格,如上图可变换为17245368
给你魔板的初始状态与目标状态，请给出由初态到目态变换数最少的变换步骤，若有多种变换方案则取字典序最小的那种。
 

 

Input
每组测试数据包括两行，分别代表魔板的初态与目态。
 

 

Output
对每组测试数据输出满足题意的变换步骤。
 

 

Sample Input
12345678
17245368
12345678
82754631
 

 

Sample Output
C
AC
 
 
----------------------------------------------------------------------------------------------------------------------------
 
直接BFS + 康托去重会TLE。
双向BFS会遇到反向BFS时处理字典序最小的问题。
 
简单的方法:
先以 " 12345678 " 为初始状态进行bfs，将并所有情况保存下来，这样可以从" 12345678 "到达任何一种情况。
但是，出状态不一定是" 12345678 "，所以我们可以进行映射。
 
例如：

初状态：4 6 2 8 5 7 3 1
末状态：3 4 8 7 2 5 1 6

可以转换成：

初状态：1 2 3 4 5 6 7 8
末状态：7 1 4 6 3 5 8 2

那么从 " 46285731 " 到 " 34872516 " 的路径　就等于　从 " 1234578 " 到 " 71463582 " 的路径。

而 " 1234578 " 到 " 71463582 " 的路径我们已经记录下来，直接递归打印出结果。

( 答案为： BCBCBCABCABCABBCCBCB )

 

＊数据里有初状态和末状态相等的情况，直接输出换行即可。

 

 

附AC代码：

   
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define SIZE 40325
using namespace std;

const int fac[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
struct ref{
    int parent;
    char op;
}ans[SIZE];

struct node{
    char s[10];
    int value;
    node(){}
    node(char * ss, const int v) : value(v){
        for(int i=0; i<8; ++i) *(s + i) = *(ss + i);
    }
};

bool vis[SIZE] = {0};
int cantor(char * s){
    bool vis[10] = {0};
    int rec, ans = 0;
    for(int i=0; i<8; ++i){
        vis[s[i]] = 1, rec = 0;
        for(int j=1; j<s[i]; ++j)
            if(!vis[j]) ++rec;
        ans += rec * fac[7 - i];
    }
    return ans + 1;
}

void swap(char * s, const int posa, const int posb){
    char tmp = *(s + posa);
    *(s + posa) = *(s + posb);
    *(s + posb) = tmp;
}

void operate(char * s, const char type){
    if(type == 0){ for(int i=0; i<4; ++i) swap(s, i, 7-i); }
    else if(type == 1) for(int i=0; i<3; ++i) swap(s, i, 3), swap(s, 4, 7 - i);
    else { swap(s, 2, 5); swap(s, 1, 2); swap(s, 1, 6); }
}

void bfs(){
    int value, k = 0;
    node begin, now, next;
    for(int i=0; i<8; ++i) begin.s[i] = i+1;
    begin.value = cantor(begin.s);
    queue<node> q;
    q.push(begin);
    int rec = 0;
    while(q.size()){
        now = q.front(); q.pop();
        for(int i=0; i<3; ++i){
            next = now;
            operate(next.s, i);
            if(!vis[ value = cantor(next.s) ]){
                vis[value] = 1;
                q.push(node(next.s, value));
                ans[value].parent = now.value;
                ans[value].op = 'A' + i;
            }
        }
    }
}

void deal(const int pos){
    if(ans[pos].parent == 1){
        putchar(ans[pos].op);
        return;
    }
    deal(ans[pos].parent);
    putchar(ans[pos].op);
}

void reflect(char * s, char * e){
    char reca[8], recb[8], ss[8];
    for(int i=0; i<8; ++i){
        reca[s[i]-1] = i, recb[e[i]-1] = i;
    }
    for(int i=0; i<8; ++i){
        *(e + recb[i]) = reca[i] + 1;
    }
}

int main(){
    //freopen("in", "r", stdin);
    char str[10], ptr[10];
    bfs();
    while(~scanf("%s%s", str, ptr)){
        if(!strcmp(str, ptr)){
            putchar('\n');
            continue;
        }
        for(int i=0; i<8; ++i) str[i] -= '0', ptr[i] -= '0';
        reflect(str, ptr);
        deal(cantor(ptr));
        putchar('\n');
    }
    return 0;
}