題目
2024/11/25 的每日一題
資料結構
- BFS / 廣度優先搜尋
- Backtracking / 回溯法
題意
方法會傳入一個二維陣列，這裡就叫他數字板。我們必須要判斷這個二維陣列在多次移動後會不會成為以下的排列。可以的話，回傳移動的次數；否則回傳 -1
[[1, 2, 3],
[4, 5, 0]]
想法
處理方式
根據題意得知
- 需要透過列舉出各種移動結果，來看哪個結果符合我們的預期。
- 對策：
- 當需要 列舉所有可能性 ，就可以使用 backtracking / 回溯法。
- 根據探索的方式，發現可以用廣度優先搜尋為基底，根據接下來的需求進行變形
- 對策：
- 由於只有空白 (
0) 的地方可以被移動進去，因此每一次移動都是以0的位置為基準- 在每一次的走訪後需要紀錄
0新的位置
- 在每一次的走訪後需要紀錄
- 根據題意，必須回傳「移動過幾次」
- 因此當每一次生成新的數字板時，必須記錄當下的深度
- 一次深度代表一次的移動
- 由於移動過程中 board 的排列會重複，因此當遇到重複的時候需要跳過
- 需要有個
visitedSet 來紀錄已經走訪過的 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 來解。因為需要講解清楚的環節很多，所以花了很多時間想該怎麼寫會比較好。
以上，如果有什麼回饋，歡迎在留言區跟我說，謝謝！
Top comments (0)