一道简单的bfs题目，关键是怎么表示状态。
康托展开
适用于全排列，比如一个排列 1 3 2 4，我们要求出它是排第几地排列
第一位：第一位比1小的排列都比这个排列小，但是没有ans+=03！
第二位：此时已经确定第一位，第一位与此排列相同，第二位小于3的排列都比排在这个排列前，ans+=12！
第三位：比2小的数只有1，但1已经出现了，ans+=0*1！
ans=2，有两个排列在它前面
solution
我们把魔板的排列用康托展开存起来，判断是否出现过即可。
点击查看代码
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=5e4+5;
struct node{
int a[10];
};
node s,e,q[N],k,w,step[N];
bool vis[N];
int h,t,p,en,jc[11],cnt,d[N],last[N],op[N],m,num;
char st[10000];
int work(node z){
int x=0,tot=0;
fo(i,1,8) {
x=0;
fo(j,1,i-1) {
if (z.a[j]<z.a[i]) ++x;
}
tot+=(z.a[i]-x-1)*jc[8-i];
}
return tot;
}
void write(int h){
if (h==1) return;
write(last[h]);
if (op[h]==1) st[++num]='A';
if (op[h]==2) st[++num]='B';
if (op[h]==3) st[++num]='C';
}
int main(){
jc[0]=1; fo(i,1,8) jc[i]=jc[i-1]*i;
fo(i,1,4) scanf("%d",&e.a[i]);
fd(i,8,5) scanf("%d",&e.a[i]);
en=work(e);
fo(i,1,4) q[1].a[i]=i;
fo(i,5,8) q[1].a[i]=8-i+5;
p=work(q[1]); vis[p]=1;
h=0; t=1;
while (h<t) {
k=q[++h];
cnt=work(k);
if (cnt==en) break;
w=k;
fo(i,1,4) swap(w.a[i],w.a[i+4]);
cnt=work(w);
if (!vis[cnt]) {
q[++t]=w; d[t]=d[h]+1; vis[cnt]=1; last[t]=h; op[t]=1;
}
w=k;
fd(i,3,1) swap(w.a[i],w.a[i+1]);
fd(i,7,5) swap(w.a[i],w.a[i+1]);
cnt=work(w);
if (!vis[cnt]) {
q[++t]=w; d[t]=d[h]+1; vis[cnt]=1; last[t]=h; op[t]=2;
}
w=k;
m=w.a[6]; w.a[6]=w.a[7]; w.a[7]=w.a[3]; w.a[3]=w.a[2]; w.a[2]=m;
cnt=work(w);
if (!vis[cnt]) {
q[++t]=w; d[t]=d[h]+1; vis[cnt]=1; last[t]=h; op[t]=3;
}
}
printf("%d\n",d[h]);
write(h);
int pd=0;
fo(i,1,num) {
++pd;
printf("%c",st[i]);
if (pd%60==0) printf("\n");
}
return 0;
}