773。滑動拼圖
難度：難
主題：陣列、廣度優先搜尋、矩陣
在 2 x 3 的棋盤上，有五個從 1 到 5 標記的圖塊，以及一個用 0 表示的空方塊。 移動 包括選擇 0 和 4 個方向相鄰的數字並交換它.
當且僅當棋盤為 [[1,2,3],[4,5,0]] 時，棋盤的狀態才得以解決。
給定拼圖板，返回解決該板的狀態所需的最少移動次數。如果棋盤狀態無法求解，則傳回-1。
範例1：
-
輸入： board = [[1,2,3],[4,0,5]]
-
輸出： 1
-
說明：一步交換 0 和 5。
範例2：
-
輸入： board = [[1,2,3],[5,4,0]]
-
輸出： -1
-
說明：無論移動多少步都無法解決棋盤問題。
範例 3：
-
輸入： board = [[4,1,2],[5,0,3]]
-
輸出： 5
-
說明： 5 是解決棋盤問題的最小步數。
- 範例路徑：
- 第 0 步後：[[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.length == 2
- 板[i].length == 3
- 0
- 每個值板[i][j]都是唯一。
提示：
- 執行廣度優先搜索，其中節點是拼圖板，邊緣是如果兩個拼圖板可以透過一次移動相互轉換。
解：
我們可以應用廣度優先搜尋（BFS）演算法。這個想法是從給定的初始狀態開始探索棋盤的所有可能配置，一次一步，直到達到已解決的狀態。
方法：
-
廣度優先搜尋（BFS）：
- BFS 在這裡是理想的選擇，因為我們正在尋找到達已解決狀態的最短路徑。
- 每個棋盤配置都可以被視為一個節點，節點之間的邊代表有效的移動，其中 0 塊與相鄰塊交換。
- BFS 將逐級探索棋盤配置，確保我們以最少的步數達到已解決的狀態。
-
國家代表：
- 我們將把棋盤表示為字串（以便於比較和儲存）。
- 解決的狀態是“123450”，因為它是棋盤 [[1,2,3],[4,5,0]] 的線性表示。
-
態轉換：
- 在每個狀態中，如果 0 塊位於棋盤的邊界內，則它可以與其 4 個相鄰塊（上、下、左、右）之一交換。
-
追蹤造訪過的州：
-
檢查已解決的狀態：
- 如果在任何時候棋盤配置與已解決的狀態匹配，我們都會返回到達該狀態所需的移動次數。
-
處理不可能的情況：
- 如果 BFS 完成並且我們沒有找到已解決的狀態，則表示不可能解決該難題，我們返回 -1。
讓我們用 PHP 實作這個解：773。滑動拼圖
解釋：
-
初始設定：我們先將 2D 板轉換為 1D 字串，以便於操作。
-
BFS 執行： 我們將棋盤的初始狀態和移動計數（從 0 開始）一起放入隊列。在每次 BFS 迭代中，我們探索可能的移動（基於 0 區塊的位置），將 0 與相鄰區塊交換，並將新狀態放入佇列。
-
訪問過的狀態：我們使用字典來追蹤訪問過的棋盤狀態，以避免重新訪問和循環回相同的狀態。
-
邊緣驗證：我們檢查任何移動是否保留在 2x3 網格的邊界內，特別是確保沒有非法移動環繞網格（例如在左邊緣向左移動或在右邊緣向右移動）。
-
回傳結果：如果我們達到目標狀態，我們會回傳移動次數。如果 BFS 完成但我們沒有達到目標，我們會回傳 -1。
時間複雜度：
-
BFS 複雜度： BFS 的時間複雜度為 O(N)，其中 N 是唯一棋盤狀態的數量。對於這個謎題，最多有 6 個！ (720) 可能的配置。
空間複雜度：
- 由於佇列和存取狀態所需的儲存空間複雜度也是 O(N)。
考慮到限制，該解決方案應該足夠有效率。
聯絡連結
如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！
如果您想要更多類似的有用內容，請隨時關注我：
以上是。滑動拼圖的詳細內容。更多資訊請關注PHP中文網其他相關文章！
