魔板
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4050 Accepted Submission(s): 951
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
思路：是先了解了康托展开再做这道题，想当于是用康拓展开给每一种状态弄一个独立的标号，可以快速找到某一种状态，所以就是先用12345678为初始状态，然后记录每一种状态的contor值，这里我用了把函数写在结构体里的方法，方便简洁（学习了网上一位大佬），然后比较难想就是，每一次输入的初态和末态并不都是12345678，如何将输入和bfs中的状态对应起来呢？
我们就需要置换一下。
置换： 原始态为“12345678” 例如 初态是 “45781236” 目态是 ”78451326“
目态的第一位‘7’ 在初态中是第三位， 而原始态的第三位是‘3’，故目态的第一位应该转换为‘3’，（就是将输入的值和12345678一一对应）就这样一次转换 最后目态转换为 34125768， 最后找出34125768对应的康拓值，输出就好了。
而字典序的话，每一次bfs都是按照ABC这样的顺序的，所以每种状态的步骤必然是最小字典序。
具体看代码。
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<bitset>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define CLR(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
using namespace std;
typedef long long ll;
const int N=40320+10;
int fact[9]= {1,1,2,6,24,120,720,5040,40320};
struct info{
int arr[8];
int val;//计算出来的康托展开的序号
string step;
void contor(){//把康托展开写在结构体里面
val=0;
for(int i=0;i<8;i++){
int t=0;
for(int j=i+1;j<8;j++){
if(arr[j]<arr[i])t++;
}
val+=t*fact[8-i-1];
}
val++;
}
void change_a(){
reverse(arr,arr+8);
step+='A';
}
void change_b(){
int temp=arr[3];
for (int i=3; i>0; --i)
arr[i]=arr[i-1];
arr[0]=temp;
temp=arr[4];
for (int i=4; i<7; ++i)
arr[i]=arr[i+1];
arr[7]=temp;
step+="B";
}
void change_c(){
int temp=arr[1];
arr[1]=arr[6];
arr[6]=arr[5];
arr[5]=arr[2];
arr[2]=temp;
step+='C';
}
};
int vis[N];
string ans[N];//记录每一种状态的操作
int re[8];
info s,t;
void bfs(){
queue<info>q;
vis[s.val]=1;
q.push(s);
info now,v;
while(!q.empty()){
now=q.front();
q.pop();
v=now;
int len=v.step.length();
if(len<1||v.step[len-1]!='A'){//去掉AA这样的情况
v.change_a();
v.contor();
if(!vis[v.val]){
vis[v.val]=1;
ans[v.val]=v.step;
q.push(v);
}
}
v=now;
if(len<3||v.step[len-1]!='B'||v.step[len-2]!='B'||v.step[len-3]!='B'){//去掉BBBB这样的情况
v.change_b();
v.contor();
if(!vis[v.val]){
vis[v.val]=1;
ans[v.val]=v.step;
q.push(v);
}
}
v=now;
if(len<3||v.step[len-1]!='C'||v.step[len-2]!='C'||v.step[len-3]!='C'){//去掉CCCC这样的情况
v.change_c();
v.contor();
if(!vis[v.val]){
vis[v.val]=1;
ans[v.val]=v.step;
q.push(v);
}
}
}
}
int main(){
for(int i=0;i<8;i++){
s.arr[i]=i+1;
}//初始化 12345678
s.contor();
bfs();
char ss[10];
while(scanf("%s",ss)!=EOF){
for(int i=0;i<8;i++){
re[ss[i]-'0']=i+1;
}//将输入的初始状态的字符 和12345678（bfs中的初始状态）一一对应
scanf("%s",ss);
for(int i=0;i<8;i++){
t.arr[i]=re[ss[i]-'0'];//找到当前的目标状态在bfs中对应的值
}
t.contor();
printf("%s
",ans[t.val].c_str());
}
}