909. Snakes And Ladders

Medium

Description

給定一個 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#

BFS 求最短路徑，關鍵在正確將格子編號轉換為棋盤座標（蛇形排列）。

棋盤是蛇形（boustrophedon）排列，需要正確轉換編號到行列座標
每個格子可以走到 +1 到 +6 的位置，若有蛇/梯則跳轉
BFS 天然找到最短步數

Approaches#

⭐1: BFS#

概念: 從格子 1 開始 BFS，每步嘗試移動 1~6 格，遇到蛇/梯則跳轉，第一次到達 n^2 即為答案
時間複雜度: O(n^2)
空間複雜度: 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（展平棋盤）#

概念: 先將蛇形棋盤展平為一維陣列，簡化後續 BFS 邏輯
時間複雜度: O(n^2)
空間複雜度: 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 最短路徑 – 將遊戲棋盤抽象為圖
關鍵技巧: 蛇形棋盤的座標轉換是本題難點；注意蛇/梯的目的地不能再跳轉（只跳一次）；visited 要在入隊時標記