解題說明
Open the Lock
題目描述：一個密碼鎖有四個轉盤，每個轉盤上有數字 0-9。每次操作可以將一個轉盤向上或向下轉動一格。給定一組死亡密碼 deadends（轉到這些組合鎖會永久鎖死）和目標密碼 target，從 "0000" 開始，求最少需要多少次轉動。如果無法到達目標，回傳 -1。
解題思路：這是一個典型的 BFS 最短路問題。每個密碼組合是一個節點，每次轉動一個轉盤產生一條邊：
- 將
deadends放入集合中，方便快速查詢。 - 從
"0000"開始 BFS，每次對四個轉盤各嘗試上轉和下轉（共 8 個鄰居）。 - 跳過已訪問的和在
deadends中的組合。 - 首次到達
target時的步數就是答案。
C++ 解法
複雜度分析
時間複雜度：O(10^4 * 4) = O(40000) — 最多有 10^4 種密碼組合，每個節點有 8 個鄰居，但每個節點最多入隊一次。
空間複雜度：O(10^4) — visited 集合和佇列最多存放所有密碼組合。
虛擬碼
1. Put deadends into a hash set
2. If "0000" is a deadend, return -1
3. BFS from "0000":
a. Initialize queue with "0000", visited set, steps = 0
b. While queue not empty:
- steps++
- For each node in current level:
- Generate 8 neighbors (4 wheels x 2 directions)
- If neighbor == target, return steps
- If not visited and not dead, add to queue
4. Return -1 (unreachable)其他解法
雙向 BFS：同時從 "0000" 和 target 兩端搜尋，每次擴展較小的那一端。在最壞情況下搜尋空間從 O(b^d) 降至 O(b^(d/2))，b 為分支因子，d 為深度。實作稍複雜但在稀疏圖上效果顯著。
A 搜尋*：用曼哈頓距離（每個轉盤到目標的最小轉動次數之和）作為啟發函數。能更快找到答案但實作複雜度更高。
延伸思考
- 如何用雙向 BFS 優化？時間複雜度能改善多少？
- 如果轉盤有 n 個（不止 4 個），時間複雜度如何變化？
- 如果每次可以同時轉動多個轉盤，問題會如何變化？