益智游戲克星：BFS暴力搜索算法

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

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

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

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

一、題目解析

LeetCode 第 773 題就是滑動拼圖問題，題目的意思如下：

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

請你寫一個算法，計算贏得游戲需要的最少移動次數(shù)，如果不能贏得游戲，返回 -1。

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

如果輸入的是board = [[1,2,3],[4,0,5]]，則算法返回 -1，因為這種局面下無論如何都不能贏得游戲。

二、思路分析

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

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

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

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

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

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

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

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

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

很簡單，我們只要手動寫出來這個映射就行了：

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

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

至此，我們就把這個問題完全轉(zhuǎn)化成標(biāo)準(zhǔn)的 BFS 問題了，借助前文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算法框架開始*******/ queueq; unordered_setvisited; q.push(start); visited.insert(start); intstep=0; while(!q.empty()){ intsz=q.size(); for(inti=0;i

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

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