滑動(dòng)拼圖游戲大家應(yīng)該都玩過(guò)，下圖是一個(gè) 4x4 的滑動(dòng)拼圖：

拼圖中有一個(gè)格子是空的，可以利用這個(gè)空著的格子移動(dòng)其他數(shù)字。你需要通過(guò)移動(dòng)這些數(shù)字，得到某個(gè)特定排列順序，這樣就算贏了。

我小時(shí)候還玩過(guò)一款叫做「華容道」的益智游戲，也和滑動(dòng)拼圖比較類似：

那么這種游戲怎么玩呢？我記得是有一些套路的，類似于魔方還原公式。但是我們今天不來(lái)研究讓人頭禿的技巧，這些益智游戲通通可以用暴力搜索算法解決，所以今天我們就學(xué)以致用，用 BFS 算法框架來(lái)秒殺這些游戲。

一、題目解析

LeetCode 第 773 題就是滑動(dòng)拼圖問(wèn)題，題目的意思如下：

給你一個(gè) 2x3 的滑動(dòng)拼圖，用一個(gè) 2x3 的數(shù)組board表示。拼圖中有數(shù)字 0~5 六個(gè)數(shù)，其中數(shù)字 0 就表示那個(gè)空著的格子，你可以移動(dòng)其中的數(shù)字，當(dāng)board變?yōu)閇[1,2,3],[4,5,0]]時(shí)，贏得游戲。

請(qǐng)你寫(xiě)一個(gè)算法，計(jì)算贏得游戲需要的最少移動(dòng)次數(shù)，如果不能贏得游戲，返回 -1。

比如說(shuō)輸入的二維數(shù)組board = [[4,1,2],[5,0,3]]，算法應(yīng)該返回 5：

如果輸入的是board = [[1,2,3],[4,0,5]]，則算法返回 -1，因?yàn)檫@種局面下無(wú)論如何都不能贏得游戲。

二、思路分析

對(duì)于這種計(jì)算最小步數(shù)的問(wèn)題，我們就要敏感地想到 BFS 算法。

這個(gè)題目轉(zhuǎn)化成 BFS 問(wèn)題是有一些技巧的，我們面臨如下問(wèn)題：

1、一般的 BFS 算法，是從一個(gè)起點(diǎn)start開(kāi)始，向終點(diǎn)target進(jìn)行尋路，但是拼圖問(wèn)題不是在尋路，而是在不斷交換數(shù)字，這應(yīng)該怎么轉(zhuǎn)化成 BFS 算法問(wèn)題呢？

2、即便這個(gè)問(wèn)題能夠轉(zhuǎn)化成 BFS 問(wèn)題，如何處理起點(diǎn)start和終點(diǎn)target？它們都是數(shù)組哎，把數(shù)組放進(jìn)隊(duì)列，套 BFS 框架，想想就比較麻煩且低效。

首先回答第一個(gè)問(wèn)題，BFS 算法并不只是一個(gè)尋路算法，而是一種暴力搜索算法，只要涉及暴力窮舉的問(wèn)題，BFS 就可以用，而且可以最快地找到答案。

你想想計(jì)算機(jī)怎么解決問(wèn)題的？哪有那么多奇技淫巧，本質(zhì)上就是把所有可行解暴力窮舉出來(lái)，然后從中找到一個(gè)最優(yōu)解罷了。

明白了這個(gè)道理，我們的問(wèn)題就轉(zhuǎn)化成了：如何窮舉出board當(dāng)前局面下可能衍生出的所有局面？這就簡(jiǎn)單了，看數(shù)字 0 的位置唄，和上下左右的數(shù)字進(jìn)行交換就行了：

這樣其實(shí)就是一個(gè) BFS 問(wèn)題，每次先找到數(shù)字 0，然后和周圍的數(shù)字進(jìn)行交換，形成新的局面加入隊(duì)列…… 當(dāng)?shù)谝淮蔚竭_(dá)target時(shí)，就得到了贏得游戲的最少步數(shù)。

對(duì)于第二個(gè)問(wèn)題，我們這里的board僅僅是 2x3 的二維數(shù)組，所以可以壓縮成一個(gè)一維字符串。其中比較有技巧性的點(diǎn)在于，二維數(shù)組有「上下左右」的概念，壓縮成一維后，如何得到某一個(gè)索引上下左右的索引？

很簡(jiǎn)單，我們只要手動(dòng)寫(xiě)出來(lái)這個(gè)映射就行了：

vector>neighbor={ {1,3}, {0,4,2}, {1,5}, {0,4}, {3,1,5}, {4,2} };

這個(gè)含義就是，在一維字符串中，索引i在二維數(shù)組中的的相鄰索引為neighbor[i]，：

至此，我們就把這個(gè)問(wèn)題完全轉(zhuǎn)化成標(biāo)準(zhǔn)的 BFS 問(wèn)題了，借助前文BFS 算法框架套路詳解的代碼框架，直接就可以套出解法代碼了：

intslidingPuzzle(vector>&board){ intm=2,n=3; stringstart=""; stringtarget="123450"; //將2x3的數(shù)組轉(zhuǎn)化成字符串 for(inti=0;i>neighbor={ {1,3}, {0,4,2}, {1,5}, {0,4}, {3,1,5}, {4,2} }; /*******BFS算法框架開(kāi)始*******/ queueq; unordered_setvisited; q.push(start); visited.insert(start); intstep=0; while(!q.empty()){ intsz=q.size(); for(inti=0;i

至此，這道題目就解決了，其實(shí)框架完全沒(méi)有變，套路都是一樣的，我們只是花了比較多的時(shí)間將滑動(dòng)拼圖游戲轉(zhuǎn)化成 BFS 算法。

很多益智游戲都是這樣，雖然看起來(lái)特別巧妙，但都架不住暴力窮舉，常用的算法就是回溯算法或者 BFS 算法，感興趣的話我們以后再聊。