給定一個
n x n的蛇梯棋盤board，從左下角格子 1 開始，目標到達格子n^2。每次可以擲骰子移動 1~6 步，到達有蛇或梯子的格子會被傳送。求最少需要幾步到達終點，若無法到達回傳-1。
Example:
Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]] Output: 4
Intuition
TIP
BFS 求最短路徑，關鍵在正確將格子編號轉換為棋盤座標（蛇形排列）。
- 棋盤是蛇形（boustrophedon）排列，需要正確轉換編號到行列座標
- 每個格子可以走到 +1 到 +6 的位置，若有蛇/梯則跳轉
- BFS 天然找到最短步數
Approaches
⭐ 1. BFS — O(n^2) / O(n^2)
- Idea: 從格子 1 開始 BFS，每步嘗試移動 1~6 格，遇到蛇/梯則跳轉，第一次到達 n^2 即為答案
- Time:
O(n^2) - Space:
O(n^2)
class Solution {
fun snakesAndLadders(board: Array<IntArray>): Int {
val n = board.size
val target = n * n
fun getCoord(num: Int): IntArray {
val r = (num - 1) / n
val c = (num - 1) % n
val row = n - 1 - r
val col = if (r % 2 == 0) c else n - 1 - c
return intArrayOf(row, col)
}
val visited = BooleanArray(target + 1)
val queue = ArrayDeque<Int>()
queue.add(1)
visited[1] = true
var steps = 0
while (queue.isNotEmpty()) {
repeat(queue.size) {
val cur = queue.removeFirst()
if (cur == target) return steps
for (dice in 1..6) {
var next = cur + dice
if (next > target) continue
val (r, c) = getCoord(next)
if (board[r][c] != -1) next = board[r][c]
if (!visited[next]) {
visited[next] = true
queue.add(next)
}
}
}
steps++
}
return -1
}
}2. BFS (flattened board) — O(n^2) / O(n^2)
- Idea: 先將蛇形棋盤展平為一維陣列，簡化後續 BFS 邏輯
- Time:
O(n^2) - Space:
O(n^2)
class Solution {
fun snakesAndLadders(board: Array<IntArray>): Int {
val n = board.size
val target = n * n
val flat = IntArray(target + 1)
var idx = 1
var leftToRight = true
for (r in n - 1 downTo 0) {
if (leftToRight) {
for (c in 0 until n) flat[idx++] = board[r][c]
} else {
for (c in n - 1 downTo 0) flat[idx++] = board[r][c]
}
leftToRight = !leftToRight
}
val visited = BooleanArray(target + 1)
val queue = ArrayDeque<Int>()
queue.add(1)
visited[1] = true
var steps = 0
while (queue.isNotEmpty()) {
repeat(queue.size) {
val cur = queue.removeFirst()
if (cur == target) return steps
for (dice in 1..6) {
var next = cur + dice
if (next > target) continue
if (flat[next] != -1) next = flat[next]
if (!visited[next]) {
visited[next] = true
queue.add(next)
}
}
}
steps++
}
return -1
}
}🔑 Takeaways
- Pattern: 圖的 BFS 最短路徑 — 將遊戲棋盤抽象為圖
- Key trick: 蛇形棋盤的座標轉換是本題難點；注意蛇/梯的目的地不能再跳轉（只跳一次）；
visited要在入隊時標記