前言

好的，首先說明一下，這里用的是字符串的方法。根據c++字符串的尿性，速度比較慢，當然也可以改成字符數組，只不過我比較懶（沒錯╭(╯^╰)╮）

---

正題

有個2*4的矩陣被稱為魔板，有三種操作
“A”：交換上下兩行；
“B”：將最右邊的一列插入最左邊；
“C”：魔板中央四格作順時針旋轉。
然后初始狀態是
1 2 3 4
8 7 6 5
然后嘞，就是嘞
給出一個狀態，要求改變到那個狀態。

---

輸入輸出（建議無視）

Input

只有一行，包括8個整數，用空格分開（這些整數在范圍 1——8 之間），表示目標狀態。

Output

Line 1: 包括一個整數，表示最短操作序列的長度。
Line 2: 在字典序中最早出現的操作序列，用字符串表示，除最后一行外，每行輸出60個字符。

Sample Input

2 6 8 4 5 7 3 1

Sample Output

7
BCABCCB

---

解題思路

這道題就是得把一塊板線性化，然后找出變化規律。然后用哈希來判斷重復優化廣搜。
將線性化之后的版轉換為數字，然后存進哈希表里判斷重復。

---

代碼

#include<cstdio> #include<iostream> #include<string> #include<algorithm> using namespace std; const int ruler[3][8]={{8,7,6,5,4,3,2,1},{4,1,2,3,6,7,8,5},{1,7,2,4,5,3,6,8}}; //變化公式 string state[100003];//狀態 string hash[100003],ss;//哈希表 int head,tail,z,x,father[100003],num[100003]; char dot[100003]; int hashm(string s)//哈希表 {int w=0;for (int i=0;i<8;i++){w=w*10+s[i]-48;}//轉成數字w%=100003;//哈希函數int i=0;while (i<100003 && hash[(w+i)%100003]!="" && hash[(w+i)%100003]!=s)i++;//定位if (hash[(w+i)%100003]=="")//如果找到空位{hash[(w+i)%100003]=s;//記錄return false;}else return true;//放回找到 } void bfs() { hashm("12345678");//記錄狀態head=0;tail=1;state[1]="12345678";//狀態記錄do{head++;//出隊for (int i=0;i<3;i++){tail++;//入隊father[tail]=head;//記錄上一個state[tail]="";//狀態為空num[tail]=num[head]+1;//記錄改變次數if (i==0) dot[tail]='A';if (i==1) dot[tail]='B';if (i==2) dot[tail]='C';//記錄操作for (int j=0;j<8;j++){state[tail]+=state[head][ruler[i][j]-1];//變化狀態}if (hashm(state[tail])) tail--;//拒絕入隊else if (state[tail]==ss) return;//找到退出}}while(head<tail); } void print(int x) {if (x==1) return;print(father[x]);//返回printf("%c",dot[x]);//輸出 } int main() {for (int i=0;i<8;i++){scanf("%d",&x);ss+=x+48;//字符串}if (ss=="12345678") printf("0");//特殊判斷else{bfs();//廣搜printf("%d\n",num[tail]);//輸出print(tail);//輸出操作} }

總結

以上是生活随笔為你收集整理的ssl1692-魔板【HSAH,bfs】的全部內容，希望文章能夠幫你解決所遇到的問題。

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