本專欄上一篇：【BFS】八數(shù)碼問題（c++基礎算法）
目錄
一.讀題
①題面
②題意
三.做題
①算法原理
②算法實現(xiàn)
Ⅰ三種基本操作
Ⅱ操作序列
Ⅲ輸出
Ⅳ一個特殊情況
四.AC代碼
最后
②題意【寬搜（難度：6）】魔板
【題目描述】
在成功地發(fā)明了魔方之后，魯比克先生發(fā)明了它的二維版本，稱作魔板。
這是一張有8個大小相同的格子的魔板：
正在上傳…重新上傳取消
我們知道魔板的每一個方格都有一種顏色。這8種顏色用前8個正整數(shù)來表示。可以用顏色的序列來表示一種魔板狀態(tài)，規(guī)定從魔板的左上角開始，沿順時針方向依次取出整數(shù)，構成一個顏色序列。
對于上圖的魔板狀態(tài)，我們用序列（1，2，3，4，5，6，7，8）來表示。這是基本狀態(tài)。
這里提供三種基本操作，分別用大寫字母“A”，“B”，“C”來表示（可以通過這些操作改變魔板的狀態(tài)）：
“A”：交換上下兩行；
“B”：將最右邊的一列插入最左邊；
“C”：魔板中央四格作順時針旋轉。
下面是對基本狀態(tài)進行操作的示范：
A:
8 7 6 5
1 2 3 4
B:
4 1 2 3
5 8 7 6
C:
1 7 2 4
8 6 3 5
對于每種可能的狀態(tài)，這三種基本操作都可以使用。
你要編程計算用最少的基本操作完成基本狀態(tài)到目標狀態(tài)的轉換，輸出基本操作序列。
【輸入格式】
只有一行，包括8個整數(shù)，用空格分開（這些整數(shù)在范圍 1——8 之間），表示目標狀態(tài)。
【輸出格式】
第一行包括一個整數(shù)，表示最短操作序列的長度。
第二行在字典序中最早出現(xiàn)的操作序列，用字符串表示，除最后一行外，每行輸出60個字符。
【樣例輸入】
2 6 8 4 5 7 3 1
【樣例輸出】
7
BCABCCB
很顯然，這道題是讓我們求12345678經(jīng)過三種變化,到目標狀態(tài) 的步數(shù)與變化操作。
這題與【BFS】八數(shù)碼問題極其相似，我就在講論兩者間的區(qū)別中，來把這題講給你。
②算法實現(xiàn) Ⅰ三種基本操作相對于八數(shù)碼的空格上下左右操作，這題有三種不同的操作。
“A”：交換上下兩行；
“B”：將最右邊的一列插入最左邊；
“C”：魔板中央四格作順時針旋轉。
下面是對基本狀態(tài)進行操作的示范：
A:
8 7 6 5
1 2 3 4
B:
4 1 2 3
5 8 7 6
C:
1 7 2 4
8 6 3 5
看到很多人都是用二維數(shù)組來搞，但我覺得沒有必要。我直接在main函數(shù)中，利用switch（）語句來進行。
“A”功能：循環(huán)j從1-4，交換a[j]?與a[9-j]。
“B”功能：循環(huán)j從1-3，交換a[j],a[4],和a[9-j],a[5].(不斷對第j列[j會不斷加1]和最后一列交換，最終達成目的)
“C”功能，直接換來換去。
重慶分公司
重慶分公司
switch(i)
{
case 1:
for(int i=1;i<=4;i++)
{
swap(ne.a[i],ne.a[9-i]);
}
break;
case 2:
for(int i=1;i<=3;i++)
{
swap(ne.a[i],ne.a[4]);
swap(ne.a[9-i],ne.a[5]);
}
break;
case 3:
swap(ne.a[3],ne.a[6]);
swap(ne.a[7],ne.a[3]);
swap(ne.a[3],ne.a[2]);
}我將每鐘情況都賦予一個序列。當此情況可行（之前沒出現(xiàn)過），先將其上一步序列賦值到它身上，在增加此次操作的序列。
for(int k=1;k<=q.front().ans;k++) ne.bz[k]=q.front().bz[k];
ne.bz[ne.ans]=i;先將操作次數(shù)輸出，再對序列操作，然后輸出。
對序列的操作：原有基礎上，強制轉換為字符，加上‘A’，減一（因為序列數(shù)為1時應輸出A，而不建議會變?yōu)锽，因此要減一）
if(ne.kt==ed.kt)
{
printf("%d\n",q.back().ans);
for(int k=1;k<=q.back().ans;k++) printf("%c",q.back().bz[k]+'A'-1);
exit(0);
}當目標狀態(tài)與初始狀態(tài)一樣時，會無法進入我的輸出語句。因此要在結尾輸出一個0（因為當出現(xiàn)上述情況時，無需操作即可達到目標狀態(tài)）
不寫注釋啦！
#includeusing namespace std;
struct node{
int kt,ans,bz[1005];
int a[10];
}st,ed;
bool b[50000];
queueq;
long kt(node t)
{
long long s=1;
for(int i=1;i<=8;i++)
{
int index=1,f=1,count=0;
for(int j=i+1;j<=8;j++)
{
if(t.a[i]>t.a[j]) count++;
f*=index++;
}
s=s+f*count;
}
return s;
}
int main()
{
for(int i=1;i<=8;i++) st.a[i]=i;
st.kt=kt(st);
b[st.kt]=1;
for(int i=1;i<=8;i++) scanf("%d",&ed.a[i]);
ed.kt=kt(ed);
q.push(st);
while(!q.empty())
{
for(int i=1;i<=3;i++)
{
node ne=q.front();
switch(i)
{
case 1:
for(int i=1;i<=4;i++)
{
swap(ne.a[i],ne.a[9-i]);
}
break;
case 2:
for(int i=1;i<=3;i++)
{
swap(ne.a[i],ne.a[4]);
swap(ne.a[9-i],ne.a[5]);
}
break;
case 3:
swap(ne.a[3],ne.a[6]);
swap(ne.a[7],ne.a[3]);
swap(ne.a[3],ne.a[2]);
}
ne.ans++;
ne.kt=kt(ne);
if(!b[ne.kt])
{
for(int k=1;k<=q.front().ans;k++) ne.bz[k]=q.front().bz[k];
ne.bz[ne.ans]=i;
b[ne.kt]=1;
q.push(ne);
if(ne.kt==ed.kt)
{
printf("%d\n",q.back().ans);
for(int k=1;k<=q.back().ans;k++) printf("%c",q.back().bz[k]+'A'-1);
exit(0);
}
}
}
q.pop();
}
printf("0");
} 我是在網(wǎng)課期間摸魚寫作的，很辛苦。給個紅心不過分吧。。。
你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
