目錄

公司主營(yíng)業(yè)務(wù)：成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)、移動(dòng)網(wǎng)站開(kāi)發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競(jìng)爭(zhēng)能力。創(chuàng)新互聯(lián)是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開(kāi)放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來(lái)的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來(lái)驚喜。創(chuàng)新互聯(lián)推出新鄉(xiāng)免費(fèi)做網(wǎng)站回饋大家。

一.讀題

二.在做題之前

1.康拓展開(kāi)

2.DFS和BFS的區(qū)別

3.棧和隊(duì)列的區(qū)別

三.做題

1.算法原理

2.算法實(shí)現(xiàn)

①隊(duì)列

②康托展開(kāi)

③標(biāo)記

四.AC代碼

---

一.讀題

作為最經(jīng)典的一道寬度優(yōu)先搜索題，它的題面并不是很難懂。

【寬搜（難度：6）】8數(shù)碼問(wèn)題

題目描述

【題意】?

在3×3的棋盤(pán)上擺有八個(gè)棋子，每個(gè)棋子上標(biāo)有1至8的某一數(shù)字。棋盤(pán)中留有一個(gè)空格，空格用0來(lái)表示。空格周圍上下左右相鄰的棋子可以移到空格中。

現(xiàn)給出原始狀態(tài)和目標(biāo)狀態(tài)，求實(shí)現(xiàn)從初始布局到目標(biāo)布局的最少步驟（初始狀態(tài)的步數(shù)為0）。

如下圖，答案為5。?

【輸入格式】
第一個(gè)3*3的矩陣是原始狀態(tài)；
第二個(gè)3*3的矩陣是目標(biāo)狀態(tài)。
【輸出格式】
輸出移動(dòng)所用最少的步數(shù)。
【樣例1輸入】
2 8 3
1 6 4
7 0 5
1 2 3
8 0 4
7 6 5
【樣例1輸出】
5

【樣例2輸入】
2 8 3
1 6 4
7 0 5
0 1 2
3 4 5
8 7 6
【樣例2輸出】
17

很顯然，這是要我們求出矩陣1通過(guò)白色方塊的上下左右移動(dòng)轉(zhuǎn)化向矩陣2的最小步數(shù)。

---

二.在做題之前

在做題之前，我們先要弄懂3個(gè)問(wèn)題。

1.康拓展開(kāi)

在這道題中，我們要利用康托展開(kāi)判斷是否重復(fù)。在文前，蒟蒻已經(jīng)寫(xiě)了一篇文章，不懂的可以去看一下：【寬搜必備】康托展開(kāi)（從公式解析到代碼實(shí)現(xiàn)）

那么，我們就可以寫(xiě)出：

int kt(int a[],int n)
{
	int s=1;
	for(int i=1;i<=n;i++)
	{
		int index=1,f=1,count=0;
		for(int j=i+1;j<=n;j++)
		{
			f*=index;
			index++;
			if(a[i]>a[j]) count++; 
		}
		s=s+count*f;
	}	
	return s;
}

2.DFS和BFS的區(qū)別

bfs 遍歷節(jié)點(diǎn)是先進(jìn)先出，dfs遍歷節(jié)點(diǎn)是先進(jìn)后出；
bfs是按層次訪問(wèn)的，dfs 是按照一個(gè)路徑一直訪問(wèn)到底，當(dāng)前節(jié)點(diǎn)沒(méi)有未訪問(wèn)的鄰居節(jié)點(diǎn)時(shí)，然后回溯到上一個(gè)節(jié)點(diǎn)，不斷的嘗試，直到訪問(wèn)到目標(biāo)節(jié)點(diǎn)或所有節(jié)點(diǎn)都已訪問(wèn)。
bfs 適用于求源點(diǎn)與目標(biāo)節(jié)點(diǎn)距離最近的情況，例如：求最短路徑。dfs 更適合于求解一個(gè)任意符合方案中的一個(gè)或者遍歷所有情況，例如：全排列、拓?fù)渑判?、求到達(dá)某一點(diǎn)的任意一條路徑。

3.棧和隊(duì)列的區(qū)別

（1）棧和隊(duì)列的出入方式不同：棧是后進(jìn)先出、隊(duì)列是先進(jìn)先出。
（2）棧和隊(duì)列在具體實(shí)現(xiàn)的時(shí)候操作的位置不同：因?yàn)闂Ｊ呛筮M(jìn)先出，它在一段進(jìn)行操作；而隊(duì)列是先進(jìn)先出，實(shí)現(xiàn)的時(shí)候在兩端進(jìn)行。

現(xiàn)在，我們搞懂了這三個(gè)問(wèn)題，就可以做題了。

---

三.做題 1.算法原理

采用BFS遍歷的方式尋找最優(yōu)路徑。

首先定義一個(gè)結(jié)構(gòu)體ma來(lái)存放八數(shù)碼的每一個(gè)狀態(tài)信息，其中包括節(jié)點(diǎn)對(duì)應(yīng)的矩陣，節(jié)點(diǎn)在BFS遍歷樹(shù)中的深度（相當(dāng)于步數(shù)），以及節(jié)點(diǎn)對(duì)應(yīng)的康托值。然后，定義visited數(shù)組存放已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)狀態(tài)。

利用隊(duì)列實(shí)現(xiàn)遍歷，具體步驟如下:

1.將初始狀態(tài)的各種信息壓入隊(duì)列中。
2.判斷隊(duì)列是否為空，若為空，退出循環(huán)，打印移動(dòng)步驟，結(jié)束。
3.取出隊(duì)頭元素判斷是否與目標(biāo)狀態(tài)一致。若一致,則退出循環(huán)，輸出移動(dòng)步驟，程序結(jié)束。若不一致,則分別判斷空格向左、向上、向下以及向右能否移動(dòng)。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?5.若可以移動(dòng)，求其康托值，然后壓進(jìn)隊(duì)列。并跳轉(zhuǎn)到步驟四。

2.算法實(shí)現(xiàn) ①隊(duì)列

因?yàn)榇岁?duì)列要存的東西是一個(gè)結(jié)構(gòu)體，因此也要把其類型定為結(jié)構(gòu)體ma

②康托展開(kāi)

在此代碼中，康托展開(kāi)用于判重。要將一個(gè)3*3的矩陣換為一個(gè)數(shù)。首先，我們要把此二維數(shù)組變?yōu)橐痪S的。

int d[10],len = 0;
    for (int i = 1; i<= 3; i++)
    {
        for (int j = 1; j<= 3; j++) 
        {
            d[++len] = ak.a[i][j];
        }
    }

然后，進(jìn)行康拓轉(zhuǎn)化。最后就是這樣

int kt(ma ak)
{
    int d[10],len = 0;
    for (int i = 1; i<= 3; i++)
    {
        for (int j = 1; j<= 3; j++) 
        {
            d[++len] = ak.a[i][j];
        }
    }
    int s=1;
    for(int i=1;i<=9;i++)
    {
        int index=1,f=1,count=0;
        for(int j=i+1;j<=9;j++)
        {
            f=f*index,index++;
            if(d[i]>d[j]) count++;
        }
        s=s+count*f;
    }
    return s;
}

③標(biāo)記

很簡(jiǎn)單，用數(shù)組flag標(biāo)記康托值即可

---

四.AC代碼

#includeusing namespace std;
struct ma{
    int a[10][10],x0,y0,ans,kt; 
};
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
queueq;
bool flag[400000];
int kt(ma ak)
{
    int d[10],len = 0;
    for (int i = 1; i<= 3; i++)
    {
        for (int j = 1; j<= 3; j++) 
        {
            d[++len] = ak.a[i][j];
        }
    }
    int s=1;
    for(int i=1;i<=9;i++)
    {
        int index=1,f=1,count=0;
        for(int j=i+1;j<=9;j++)
        {
            f=f*index,index++;
            if(d[i]>d[j]) count++;
        }
        s=s+count*f;
    }
    return s;
}
int main()
{
    ma shi,mo;
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            scanf("%d",&shi.a[i][j]);
            if(shi.a[i][j]==0)
            {
                shi.x0=i,shi.y0=j;
            }
        }
    }
    shi.ans = 0;
    shi.kt = kt(shi);
    flag[shi.kt] = 1;
    q.push(shi);
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            scanf("%d",&mo.a[i][j]);
        }
    }
    mo.kt=kt(mo);
    while(!q.empty())//q非空，可以走
    {
        for(int i=0;i<4;i++)//四個(gè)方向
        {
            ma ac=q.front();
            int nx = ac.x0 + dx[i];
            int ny = ac.y0+ dy[i];
            if(nx>=1&&ny>=1&&nx<=3&&ny<=3)
            {
                swap(ac.a[ac.x0][ac.y0],ac.a[nx][ny]);
                ac.x0=nx;
                ac.y0=ny;
                //將0與目標(biāo)數(shù)交換
                ac.ans++;//步數(shù)加1
                ac.kt=kt(ac);
                //康托判重
                 if (!flag[ac.kt])
                {
                    flag[ac.kt] = 1;
                    q.push(ac);
                    //加入隊(duì)列
                    if(ac.kt==mo.kt)
                    { 
                        printf("%d",q.back().ans);
                        exit(0);
                    }
                }
            }
        }
        q.pop();
        //彈出已遍歷完所有情況的矩陣
    }
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章題目：【BFS】八數(shù)碼問(wèn)題（c++基礎(chǔ)算法）-創(chuàng)新互聯(lián)
文章地址：http://jinyejixie.com/article48/dijchp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁(yè)設(shè)計(jì)公司、微信小程序、營(yíng)銷型網(wǎng)站建設(shè)、虛擬主機(jī)、域名注冊(cè)、用戶體驗(yàn)

廣告

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