本專欄上一篇：【BFS】八數(shù)碼問題（c++基礎(chǔ)算法）

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴，公司提供的服務(wù)項目有：域名注冊、網(wǎng)站空間、營銷軟件、網(wǎng)站建設(shè)、碾子山網(wǎng)站維護(hù)、網(wǎng)站推廣。

---

目錄

一.讀題

①題面

②題意

三.做題

①算法原理

②算法實現(xiàn)

Ⅰ三種基本操作

Ⅱ操作序列

Ⅲ輸出

Ⅳ一個特殊情況

四.AC代碼

最后

---

一.讀題 ①題面

【寬搜（難度：6）】魔板

【題目描述】
在成功地發(fā)明了魔方之后，魯比克先生發(fā)明了它的二維版本，稱作魔板。
這是一張有8個大小相同的格子的魔板：
正在上傳…重新上傳取消
我們知道魔板的每一個方格都有一種顏色。這8種顏色用前8個正整數(shù)來表示?？梢杂妙伾男蛄衼肀硎疽环N魔板狀態(tài)，規(guī)定從魔板的左上角開始，沿順時針方向依次取出整數(shù)，構(gòu)成一個顏色序列。
對于上圖的魔板狀態(tài)，我們用序列（1，2，3，4，5，6，7，8）來表示。這是基本狀態(tài)。
這里提供三種基本操作，分別用大寫字母“A”，“B”，“C”來表示（可以通過這些操作改變魔板的狀態(tài)）：
“A”：交換上下兩行；
“B”：將最右邊的一列插入最左邊；
“C”：魔板中央四格作順時針旋轉(zhuǎn)。
下面是對基本狀態(tài)進(jìn)行操作的示范：
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)到目標(biāo)狀態(tài)的轉(zhuǎn)換，輸出基本操作序列。
【輸入格式】
只有一行，包括8個整數(shù)，用空格分開（這些整數(shù)在范圍 1——8 之間），表示目標(biāo)狀態(tài)。
【輸出格式】
第一行包括一個整數(shù)，表示最短操作序列的長度。
第二行在字典序中最早出現(xiàn)的操作序列，用字符串表示，除最后一行外，每行輸出60個字符。
【樣例輸入】
2 6 8 4 5 7 3 1
【樣例輸出】
7
BCABCCB

②題意

很顯然，這道題是讓我們求12345678經(jīng)過三種變化,到目標(biāo)狀態(tài) 的步數(shù)與變化操作。

---

三.做題 ①算法原理

這題與【BFS】八數(shù)碼問題極其相似，我就在講論兩者間的區(qū)別中，來把這題講給你。

②算法實現(xiàn) Ⅰ三種基本操作

相對于八數(shù)碼的空格上下左右操作，這題有三種不同的操作。

“A”：交換上下兩行；
“B”：將最右邊的一列插入最左邊；
“C”：魔板中央四格作順時針旋轉(zhuǎn)。
下面是對基本狀態(tài)進(jìn)行操作的示范：
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（）語句來進(jìn)行。

“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]和最后一列交換，最終達(dá)成目的)

“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]);
			}

Ⅱ操作序列

我將每鐘情況都賦予一個序列。當(dāng)此情況可行（之前沒出現(xiàn)過），先將其上一步序列賦值到它身上，在增加此次操作的序列。

for(int k=1;k<=q.front().ans;k++) ne.bz[k]=q.front().bz[k];
	ne.bz[ne.ans]=i;

Ⅲ輸出

先將操作次數(shù)輸出，再對序列操作，然后輸出。

對序列的操作：原有基礎(chǔ)上，強制轉(zhuǎn)換為字符，加上‘A’，減一（因為序列數(shù)為1時應(yīng)輸出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); 
    }

Ⅳ一個特殊情況

當(dāng)目標(biāo)狀態(tài)與初始狀態(tài)一樣時，會無法進(jìn)入我的輸出語句。因此要在結(jié)尾輸出一個0（因為當(dāng)出現(xiàn)上述情況時，無需操作即可達(dá)到目標(biāo)狀態(tài)）

---

四.AC代碼

不寫注釋啦！

#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)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享標(biāo)題：【BFS】魔板（c++基礎(chǔ)算法）-創(chuàng)新互聯(lián)
標(biāo)題路徑：http://chinadenli.net/article36/ddijsg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、全網(wǎng)營銷推廣、App設(shè)計、App開發(fā)、商城網(wǎng)站、云服務(wù)器

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)