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
Author LL
第一道康拓展开题，由于魔板的第二行，由于是逆向的，所以我处理的时候将其看做是摆正的
也就是
1234
8765
而我处理的时候是
1234
5678
康拓展开的原理考研看这里：http://blog.csdn.net/zhongkeli/article/details/6966805
知道了原理之后，就不难解决了
#include#include #include #include #include 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 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; }