12345678 17245368 12345678 82754631
C AC
第一道康拓展开题，由于魔板的第二行，由于是逆向的，所以我处理的时候将其看做是摆正的
也就是
1234
8765
而我处理的时候是
1234
5678
康拓展开的原理考研看这里：http://blog.csdn.net/zhongkeli/article/details/6966805
知道了原理之后，就不难解决了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
string start,end,ans[50000];
int hash[10],pos[10],vis[50000];
struct node
{
string step,str;
int val;
};
int solve(string &s)
{
int i,j,sum = 0;
for(i = 0; i<7; i++)
{
int cnt = 0;
for(j = i+1; j<8; j++)
if(s[i]>s[j])
cnt++;
sum+=cnt*hash[7-i];
}
return sum;
}
void fun_A(string &s)
{
for(int i = 0; i<4; i++)
swap(s[i],s[i+4]);
}
void fun_B(string &s)
{
char t=s[3];
for(int i=2; i>=0; i--)
s[i+1]=s[i];
s[0]=t;
t=s[7];
for(int i=6; i>=4; i--)
s[i+1]=s[i];
s[4]=t;
}
void fun_C(string &s)
{
char t=s[1];
s[1]=s[5];
s[5]=s[6];
s[6]=s[2];
s[2]=t;
}
void bfs()
{
memset(vis,0,sizeof(vis));
node a,next;
queue<node> Q;
a.step = "";
a.str = start;
a.val = solve(start);
vis[a.val] = 1;
ans[a.val] = "";
Q.push(a);
while(!Q.empty())
{
a = Q.front();
Q.pop();
string t;
int k;
t = a.str;
fun_A(t);
k = solve(t);
while(!vis[k])
{
vis[k] = 1;
next = a;
next.step+=‘A‘;
ans[k] = next.step;
next.str = t;
next.val = k;
Q.push(next);
}
t = a.str;
fun_B(t);
k = solve(t);
while(!vis[k])
{
vis[k] = 1;
next = a;
next.step+=‘B‘;
ans[k] = next.step;
next.str = t;
next.val = k;
Q.push(next);
}
t = a.str;
fun_C(t);
k = solve(t);
while(!vis[k])
{
vis[k] = 1;
next = a;
next.step+=‘C‘;
ans[k] = next.step;
next.str = t;
next.val = k;
Q.push(next);
}
}
}
int main()
{
int i,j;
hash[0] = 1;
for(i = 1; i<10; i++)
hash[i] = hash[i-1]*i;
start = "12345678";
bfs();
while(cin>>start>>end)
{
swap(start[4],start[7]);//把魔板板变为我所处理的状况
swap(start[6],start[5]);
swap(end[4],end[7]);
swap(end[6],end[5]);
for(i = 0; i<8; i++)
pos[start[i]-‘0‘] = i+1;
for(i = 0; i<8; i++)
end[i] = pos[end[i]-‘0‘];
int k;
k = solve(end);
cout << ans[k] << endl;
}
return 0;
}
HDU1430:魔板(康托展开),布布扣,bubuko.com
原文：http://blog.csdn.net/libin56842/article/details/22753077