1. 題目

在一個 2 x 3 的板上（board）有 5 塊磚瓦，用數(shù)字 1~5 來表示, 以及一塊空缺用 0 來表示.

一次移動定義為選擇 0 與一個相鄰的數(shù)字（上下左右）進行交換.

最終當板 board 的結(jié)果是 [[1,2,3],[4,5,0]] 謎板被解開。

給出一個謎板的初始狀態(tài)，返回最少可以通過多少次移動解開謎板，如果不能解開謎板，則返回 -1 。

示例： 輸入：board = [[1,2,3],[4,0,5]] 輸出：1 解釋：交換 0 和 5 ，1 步完成輸入：board = [[1,2,3],[5,4,0]] 輸出：-1 解釋：沒有辦法完成謎板輸入：board = [[4,1,2],[5,0,3]] 輸出：5 解釋： 最少完成謎板的最少移動次數(shù)是 5 ， 一種移動路徑: 尚未移動: [[4,1,2],[5,0,3]] 移動 1 次: [[4,1,2],[0,5,3]] 移動 2 次: [[0,1,2],[4,5,3]] 移動 3 次: [[1,0,2],[4,5,3]] 移動 4 次: [[1,2,0],[4,5,3]] 移動 5 次: [[1,2,3],[4,5,0]]輸入：board = [[3,2,4],[1,5,0]] 輸出：14提示： board 是一個如上所述的 2 x 3 的數(shù)組. board[i][j] 是一個 [0, 1, 2, 3, 4, 5] 的排列.

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/sliding-puzzle
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. BFS解題

類似于上圖的拼圖游戲，問到達某一狀態(tài)的最小移動步數(shù)。

類似題目：LeetCode 1284. 轉(zhuǎn)化為全零矩陣的最少反轉(zhuǎn)次數(shù)（BFS & 矩陣狀態(tài)編碼解碼）

• BFS，隊列push地圖的初始狀態(tài)
• 將隊列里的狀態(tài)取出，還原地圖，按著幾個方向移動0，生成的新的狀態(tài)，push進隊列

class Solution {vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};int m, n, i, j, k, step = 0, size, x, y; public:int slidingPuzzle(vector<vector<int>>& board) {m = board.size(), n = board[0].size();string ans = "123450", state;int x0, y0, xi, yi;pair<int,int> xy0;//0的坐標queue<string> q;unordered_set<string> visited;//訪問標記集合state = boardToString(board);//初始狀態(tài)if(state == ans)return step;q.push(state);visited.insert(state);while(!q.empty()){step++;size = q.size();while(size--){xy0 = stringToBoard(q.front(), board);//還原地圖，并得到0的坐標q.pop();x0 = xy0.first;y0 = xy0.second;for(k = 0; k < 4; ++k){ //0可以4個方向交換xi = x0+dir[k][0];yi = y0+dir[k][1];if(xi>=0 && xi<m && yi>=0 && yi<n){swap(board[xi][yi], board[x0][y0]);//交換state = boardToString(board);//新的狀態(tài)if(state == ans)return step;if(!visited.count(state))//沒有出現(xiàn)過該地圖{visited.insert(state);q.push(state);}swap(board[xi][yi], board[x0][y0]);//還原現(xiàn)場}}}}return -1;}string boardToString(vector<vector<int>>& board) { //地圖轉(zhuǎn)成字符串string s;for (i = 0; i < m; i++)for(j = 0; j < n; j++)s.push_back(board[i][j]+'0');return s;}pair<int,int> stringToBoard(string &s, vector<vector<int>>& board){ //字符串還原成地圖，并return 0的坐標，方便下次挪動for (i = m-1; i >= 0; i--)for(j = n-1; j >= 0; j--){board[i][j] = s.back()-'0';s.pop_back();if(board[i][j] == 0)x = i, y = j;}return make_pair(x, y);} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 773. 滑动谜题（BFS 地图状态转换的最短距离）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。