DEV Community

vc7
vc7

Posted on

1 1

LeetCode in Swift - 773. Sliding Puzzle (中文解釋)

題目

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 來解。因為需要講解清楚的環節很多,所以花了很多時間想該怎麼寫會比較好。

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

Sentry growth stunted Image

If you are wasting time trying to track down the cause of a crash, it’s time for a better solution. Get your crash rates to zero (or close to zero as possible) with less time and effort.

Try Sentry for more visibility into crashes, better workflow tools, and customizable alerts and reporting.

Switch Tools 🔁

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay