讀完本文，你可以去力扣拿下如下題目：

773.滑動謎題

-----------

滑動拼圖遊戲大家應該都玩過，下圖是一個 4x4 的滑動拼圖：

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

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

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

一、題目解析

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

給你一個 2x3 的滑動拼圖，用一個 2x3 的陣列 board 表示。拼圖中有數字 0~5 六個數，其中數字 0 就表示那個空著的格子，你可以移動其中的數字，當 board 變為 [[1,2,3],[4,5,0]] 時，贏得遊戲。

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

比如說輸入的二維陣列 board = [[4,1,2],[5,0,3]]，演算法應該返回 5：

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

二、思路分析

對於這種計算最小步數的問題，我們就要敏感地想到 BFS 演算法。

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

1、一般的 BFS 演算法，是從一個起點 start 開始，向終點 target 進行尋路，但是拼圖問題不是在尋路，而是在不斷交換數字，這應該怎麼轉化成 BFS 演算法問題呢？

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

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

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

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

這樣其實就是一個 BFS 問題，每次先找到數字 0，然後和周圍的數字進行交換，形成新的局面加入佇列…… 當第一次到達 target 時，就得到了贏得遊戲的最少步數。

對於第二個問題，我們這裡的 board 僅僅是 2x3 的二維陣列，所以可以壓縮成一個一維字串。其中比較有技巧性的點在於，二維陣列有「上下左右」的概念，壓縮成一維後，如何得到某一個索引上下左右的索引？

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

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

這個含義就是，在一維字串中，索引 i 在二維陣列中的的相鄰索引為 neighbor[i]，：

至此，我們就把這個問題完全轉化成標準的 BFS 問題了，藉助前文 BFS 演算法框架 的程式碼框架，直接就可以套出解法程式碼了：

int slidingPuzzle(vector<vector<int>>& board) {    int m = 2, n = 3;    string start = "";    string target = "123450";    // 將 2x3 的陣列轉化成字串    for (int i = 0; i < m; i++) {        for (int j = 0; j < n; j++) {            start.push_back(board[i][j] + '0');        }    }    // 記錄一維字串的相鄰索引    vector<vector<int>> neighbor = {        { 1, 3 },        { 0, 4, 2 },        { 1, 5 },        { 0, 4 },        { 3, 1, 5 },        { 4, 2 }    };        /******* BFS 演算法框架開始 *******/    queue<string> q;    unordered_set<string> visited;    q.push(start);    visited.insert(start);        int step = 0;    while (!q.empty()) {        int sz = q.size();        for (int i = 0; i < sz; i++) {            string cur = q.front(); q.pop();            // 判斷是否達到目標局面            if (target == cur) {                return step;            }            // 找到數字 0 的索引            int idx = 0;            for (; cur[idx] != '0'; idx++);            // 將數字 0 和相鄰的數字交換位置            for (int adj : neighbor[idx]) {                string new_board = cur;                swap(new_board[adj], new_board[idx]);                // 防止走回頭路                if (!visited.count(new_board)) {                    q.push(new_board);                    visited.insert(new_board);                }            }        }        step++;    }    return -1;    /******* BFS 演算法框架結束 *******/}

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

很多益智遊戲都是這樣，雖然看起來特別巧妙，但都架不住暴力窮舉，常用的演算法就是回溯演算法或者 BFS 演算法。