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

題目

2024/11/25 的每日一題

資料結構

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

題意

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

[[1, 2, 3],
 [4, 5, 0]]

想法

處理方式

根據題意得知

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

資料結構整形

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

[[1, 2, 3], -> [1, 2, 3, 4, 0, 5]
 [4, 0, 5]]

let board = board.reduce(into: [Int]()) { $0.append(contentsOf: $1 )}

探索路線

在 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]

路線表 / 對照表

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
}

Routine

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

準備

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

走訪過程

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

提前結束條件

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

列舉

根據當前的 index 從「路線表」找出對應的新位置。
根據所有新位置生成新的數字板
- 當新的數字板有在 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
    }
}

結語

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

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

Blog