DEV Community

vc7
vc7

Posted on

LeetCode in Swift - 773. Sliding Puzzle （中文解釋）

#swift #leetcode #中文

題目

2024/11/25 的每日一題

資料結構

  • BFS / 廣度優先搜尋
  • Backtracking / 回溯法

題意

方法會傳入一個二維陣列，這裡就叫他數字板。我們必須要判斷這個二維陣列在多次移動後會不會成為以下的排列。可以的話，回傳移動的次數；否則回傳 -1

[[1, 2, 3], [4, 5, 0]]
Enter fullscreen mode Exit fullscreen mode

想法

處理方式

Concept

根據題意得知

  • 需要透過列舉出各種移動結果，來看哪個結果符合我們的預期。
    • 對策：
      • 當需要 列舉所有可能性 ，就可以使用 backtracking / 回溯法。
      • 根據探索的方式，發現可以用廣度優先搜尋為基底，根據接下來的需求進行變形
  • 由於只有空白 (0) 的地方可以被移動進去，因此每一次移動都是以 0 的位置為基準
    • 在每一次的走訪後需要紀錄 0 新的位置
  • 根據題意，必須回傳「移動過幾次」
    • 因此當每一次生成新的數字板時，必須記錄當下的深度
    • 一次深度代表一次的移動
  • 由於移動過程中 board 的排列會重複，因此當遇到重複的時候需要跳過
    • 需要有個 visited Set 來紀錄已經走訪過的 board 排列

資料結構整形

因為二維陣列不容易進行存取和更新，考慮到易讀性，在開始處理前可以降一個維度成為一維陣列，進行 swapping 時的寫法會比較簡潔。

[[1, 2, 3], -> [1, 2, 3, 4, 0, 5] [4, 0, 5]]
Enter fullscreen mode Exit fullscreen mode 
let board = board.reduce(into: [Int]()) { $0.append(contentsOf: $1 )}
Enter fullscreen mode Exit fullscreen mode

探索路線

在 backtracking 列舉的過程中，我們必須要根據能和當下 0 交換的位置生成新的數字板。

二維陣列對照到一維陣列的 indices 

 [0][1][2] [0][1][2][3][4][5] ----------- ------------------ [[1, 2, 3], -> [1, 2, 3, 4, 0, 5] [4, 0, 5]] ----------- [3][4][5]
Enter fullscreen mode Exit fullscreen mode

路線表 / 對照表

0 的位置 能交換的位置 二維陣列中的相對位置
[0] 1, 3 右、下
[1] 0, 2, 4 左、右、下
[2] 1, 5 左、下
[3] 0, 4 上、右
[4] 1, 3, 5 上、左、右
[5] 2, 4 上、左

為了易讀性的資料結構

根據以上的說明可以知道每一次的走訪需要三個資訊

  • 0 的位置
  • 數字板的樣子
  • 當前深度或移動次數

為了易讀性，與其使用大於等於 3 個元素的 tuple ，我宣告了一個結構：

struct Item { /// 0 的位置 let index: Int /// 數字板的樣子 let board: [Int] /// 當前深度或移動次數 let depth: Int }
Enter fullscreen mode Exit fullscreen mode

Routine

在文章一開始有提到會使用 BFS 為基礎演算法解題，因此會有一個主要的 queue 來暫存每一層列舉的結果。

準備

  1. Queue - 儲存列舉的結果。用來進行 BFS 走訪的主資料結構。
  2. Visited - 儲存已經走訪過的數字板排列。

走訪過程

取出 queue ("dequeue") 中第一個物件來處理。

提前結束條件

當前物件的 board 為預期結果時，回傳當前的深度（移動次數）。

列舉

  1. 根據當前的 index 從「路線表」找出對應的新位置。
  2. 根據所有新位置生成新的數字板
    • 當新的數字板有在 visited 出現過，跳過不處理
    • 沒出現過的話
      • 把新的 0 的位置、數字板樣式、加 1 後的深度組合起來存入 queue
      • 把新的數字板樣式存入 visited

走訪完成 - Queue 為空

當這個 queue 為空時，代表沒有沒有達成「提前結束條件」，也就意味著傳入的二維陣列無論如何移動都無法達成 [1, 2, 3, 4, 5, 0] ，因此回傳 -1 。

程式碼

接下來就可以根據以上的說明和 routine 來寫成程式碼了：

class Solution { /// 路線圖。因為這是靜態不需要改變，因此可以宣告為 member property 。 private let routes = [ [1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4] ] /// 預期結果。因為這是靜態不需要改變，因此可以宣告為 member property 。 private let target = [1, 2, 3, 4, 5, 0] /// LeetCode 的進入點 func slidingPuzzle(_ board: [[Int]]) -> Int { // MARK: - 1. 初始處理 /// 把二維陣列降為一維陣列，作為初始數字板 let board = board.reduce(into: [Int]()) { $0.append(contentsOf: $1 )} /// 取得初始數字板 0 的所在位置 /// 根據題目限制這邊理應不會失敗，若失敗了視為無法達成題目要求回傳 -1 。 guard let index = board.firstIndex(of: 0) else { return -1 } // MARK: - 2. BFS 的準備 var queue = [Item(index: index, board: board, depth: 0)] var visited: Set<[Int]> = [board] // MARK: - 3. Routine while !queue.isEmpty { let item = queue.removeFirst() guard item.board != target else { return item.depth } // 根據新位置列舉 for next in routes[item.index] { var board = item.board board[next] = item.board[item.index] board[item.index] = item.board[next] // 只處理未出現過的數字板 if !visited.contains(board) { queue.append(Item(index: next, board: board, depth: item.depth + 1)) visited.insert(board) } } } // MARK: - 4. End of Routine return -1 } // MARK: Data Type struct Item { let index: Int let board: [Int] let depth: Int } }
Enter fullscreen mode Exit fullscreen mode

結語

這題難是難在拆解題意，和怎麼把題意套進 BFS 來解。因為需要講解清楚的環節很多，所以花了很多時間想該怎麼寫會比較好。

以上，如果有什麼回饋，歡迎在留言區跟我說，謝謝！

Top comments (0)