2227 - 【魔板】
在魔方风靡全球之后不久，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
给你魔板的初始状态与目标状态，请给出由初态到目态变换数最少的变换步骤，若有多种变换方案则取字典序最小的那种。
Input
每组测试数据包括两行，分别代表魔板的初态与目态。
Output
对每组测试数据输出满足题意的变换步骤。
Examples
Input
12345678 17245368 12345678 82754631
Output
C AC
Solution C++
#include <cstdio> #include <cstring> #include <string> #include <queue> #include <iostream> const int M = 50000; using namespace std; struct node{ string s, path; int val; }; const int f[] = {1, 1, 2, 6, 24, 120, 720, 5040, 5040*8}; string ans[M]; bool vis[M]; int cal(string s){ //康拓 int sum = 0; for(int i = 0; i < 8; ++ i){ int cnt = 0; for(int j = i+1; j < 8; ++ j) if(s[j] < s[i]) ++cnt; sum += cnt*f[7-i]; } return sum; } string tran(string s, int num){ //转换 //string res = ""; int i; if(num == 0){ for(i = 0; i < 4; ++ i){ swap(s[i], s[i+4]); } } else if(num == 1){ char t= s[3]; for(i = 2; i >= 0; -- i) s[i+1] = s[i]; s[0] = t; t = s[7]; for(i = 6; i >= 4; -- i) s[i+1] = s[i]; s[4] = t; } else{ char t = s[1]; s[1] = s[5]; s[5] = s[6]; s[6] = s[2]; s[2] = t; } return s; } void bfs(string st){ //遍历 memset(vis, 0, sizeof(vis)); queue<node > q; node t; t.s = st; t.val = cal(t.s); t.path = ""; ans[t.val] = t.path; vis[t.val] = 1; q.push(t); while(!q.empty()){ node temp = q.front(); q.pop(); for(int i = 0; i < 3; ++ i){ node cur = temp; cur.path += (i+'A'); string a = tran(cur.s, i); int k = cal(a); if(!vis[k]){ cur.s = a; cur.val = k; ans[cur.val] = cur.path; vis[k] = 1; q.push(cur); } } } } int main(){ string st = "12345678"; bfs(st); string en, ss; int i; while(cin >> ss >> en){ swap(ss[4], ss[7]); //因为我是按照12345678这样来的，而不是按照题意顺时针的，所以要交换 swap(ss[5], ss[6]); swap(en[4], en[7]); swap(en[5], en[6]); string mm(8, 'a'); for(i = 0; i < 8; ++ i) mm[ss[i]-'0'] = i+'1'; //下面的两个for循环就是置换 // ss.clear(); string de; for(i = 0; i < 8; ++ i) de += mm[en[i]-'0']; // cout << de<<endl; int k = cal(de); cout << ans[k]<<endl; } return 0; }