魔板

Time Limit: 10000/5000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2921????Accepted Submission(s): 649

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

?

Sample Output C AC

?

題目鏈接：HDU 1430

原來思路是就用康托展開映射然后每一次都從S搜索到T然而T了。

然后改為預處理，從12345678開始把其他狀態全部搜完并記錄，O(1)輸出，但是由于一開始的S不一定是12345678，因此要用一個映射數組refl[]來記錄S與12345678的關系，然后根據這個關于把T也轉換成相對應的關系，之后還是WA很久，后來發現是第二種變化的后半部分循環反了（囧）……

按照A、B、C的順序變化使得達到的某一狀態都是最優解即長度最小的情況下字典序也最小（也可以用優先隊列來實現就是速度慢了點），然后加了個沒什么用的剪枝防止出現AA、BBBB、CCCC這樣又變回原來狀態的無意義操作。把康托展開寫在結構體里簡直方便的不行……

給一組測試數據

63728145
86372541

ACBBBCBBCBCBCABB

這組能過的話基本上就可以A了

代碼：

#include<iostream> #include<algorithm> #include<cstdlib> #include<sstream> #include<cstring> #include<bitset> #include<cstdio> #include<string> #include<deque> #include<stack> #include<cmath> #include<queue> #include<set> #include<map> using namespace std; #define INF 0x3f3f3f3f #define CLR(x,y) memset(x,y,sizeof(x)) #define LC(x) (x<<1) #define RC(x) ((x<<1)+1) #define MID(x,y) ((x+y)>>1) typedef pair<int,int> pii; typedef long long LL; const double PI=acos(-1.0); const int N=40320+10; int fact[9]={1,1,2,6,24,120,720,5040,40320}; struct info {int arr[8];int val;string step;void cantor(){val=0;for (int i=0; i<8; ++i){int k=0;for (int j=i+1; j<8; ++j){if(arr[j]<arr[i])++k;}val+=k*fact[7-i];}}void change_A(){reverse(arr,arr+8);step+="A";}void change_B(){int temp=arr[3];for (int i=3; i>0; --i)arr[i]=arr[i-1];arr[0]=temp;temp=arr[4];for (int i=4; i<7; ++i)arr[i]=arr[i+1];arr[7]=temp;step+="B";}void change_C(){int temp=arr[2];arr[2]=arr[1];arr[1]=arr[6];arr[6]=arr[5];arr[5]=temp;step+="C";} }; info S,T; char s[10]; int vis[N]; string ans[N]; int refl[10]; void bfs() {CLR(vis,0);queue<info>Q;vis[S.val]=1;Q.push(S);info now,v;while (!Q.empty()){now=Q.front();Q.pop();int len=(int)now.step.length();if(len<1||now.step[len-1]!='A'){v=now;v.change_A();v.cantor();if(!vis[v.val]){vis[v.val]=1;ans[v.val]=v.step;Q.push(v);}}if(len<3||now.step[len-1]!='B'||now.step[len-2]!='B'||now.step[len-3]!='B'){v=now;v.change_B();v.cantor();if(!vis[v.val]){vis[v.val]=1;ans[v.val]=v.step;Q.push(v);}}if(len<3||now.step[len-1]!='C'||now.step[len-2]!='C'||now.step[len-3]!='C') {v=now;v.change_C();v.cantor();if(!vis[v.val]){vis[v.val]=1;ans[v.val]=v.step;Q.push(v);}}} } int main(void) {int i;for (i=0; i<8; ++i)S.arr[i]=i+1;S.cantor();bfs();while (~scanf("%s",s)){for (i=0; i<8; ++i)refl[s[i]-'0'-1]=i+1;scanf("%s",s);for (i=0; i<8; ++i)T.arr[i]=refl[s[i]-'0'-1];T.cantor();printf("%s\n",ans[T.val].c_str());}return 0; }

轉載于:https://www.cnblogs.com/Blackops/p/5821551.html

總結

以上是生活随笔為你收集整理的HDU 1430 魔板（康托展开+BFS+预处理）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。