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
給你魔板的初始狀態與目標狀態,請給出由初態到目態變換數最少的變換步驟,若有多種變換方案則取字典序最小的那種。
Input
每組測試數據包括兩行,分別代表魔板的初態與目態。
Output
對每組測試數據輸出滿足題意的變換步驟。
Sample Input
12345678 17245368 12345678 82754631
C AC
第一道康拓展開題,由於魔板的第二行,由於是逆向的,所以我處理的時候將其看做是擺正的
也就是
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; }