HDU-1430-魔板( 康托展开 + BFS预处理 )
魔板
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
给你魔板的初始状态与目标状态，请给出由初态到目态变换数最少的变换步骤，若有多种变换方案则取字典序最小的那种。
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;
}
