。滑動拼圖

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]都是唯一。

提示：

1. 執行廣度優先搜索，其中節點是拼圖板，邊緣是如果兩個拼圖板可以透過一次移動相互轉換。

解：

我們可以應用廣度優先搜尋（BFS）演算法。這個想法是從給定的初始狀態開始探索棋盤的所有可能配置，一次一步，直到達到已解決的狀態。

方法：

1. 廣度優先搜尋（BFS）：

   • BFS 在這裡是理想的選擇，因為我們正在尋找到達已解決狀態的最短路徑。
   • 每個棋盤配置都可以被視為一個節點，節點之間的邊代表有效的移動，其中 0 塊與相鄰塊交換。
   • BFS 將逐級探索棋盤配置，確保我們以最少的步數達到已解決的狀態。

2. 國家代表：

   • 我們將把棋盤表示為字串（以便於比較和儲存）。
   • 解決的狀態是“123450”，因為它是棋盤 [[1,2,3],[4,5,0]] 的線性表示。

3. 態轉換：

   • 在每個狀態中，如果 0 塊位於棋盤的邊界內，則它可以與其 4 個相鄰塊（上、下、左、右）之一交換。

4. 追蹤造訪過的州：

   • 我們需要追蹤訪問過的狀態以避免循環和冗餘計算。

5. 檢查已解決的狀態：

   • 如果在任何時候棋盤配置與已解決的狀態匹配，我們都會返回到達該狀態所需的移動次數。

6. 處理不可能的情況：

   • 如果 BFS 完成並且我們沒有找到已解決的狀態，則表示不可能解決該難題，我們返回 -1。

讓我們用 PHP 實作這個解：773。滑動拼圖

解釋：

• 初始設定：我們先將 2D 板轉換為 1D 字串，以便於操作。
• BFS 執行： 我們將棋盤的初始狀態和移動計數（從 0 開始）一起放入隊列。在每次 BFS 迭代中，我們探索可能的移動（基於 0 區塊的位置），將 0 與相鄰區塊交換，並將新狀態放入佇列。
• 訪問過的狀態：我們使用字典來追蹤訪問過的棋盤狀態，以避免重新訪問和循環回相同的狀態。
• 邊緣驗證：我們檢查任何移動是否保留在 2x3 網格的邊界內，特別是確保沒有非法移動環繞網格（例如在左邊緣向左移動或在右邊緣向右移動）。
• 回傳結果：如果我們達到目標狀態，我們會回傳移動次數。如果 BFS 完成但我們沒有達到目標，我們會回傳 -1。

時間複雜度：

• BFS 複雜度： BFS 的時間複雜度為 O(N)，其中 N 是唯一棋盤狀態的數量。對於這個謎題，最多有 6 個！ (720) 可能的配置。

空間複雜度：

• 由於佇列和存取狀態所需的儲存空間複雜度也是 O(N)。

考慮到限制，該解決方案應該足夠有效率。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。滑動拼圖的詳細內容。更多資訊請關注PHP中文網其他相關文章！