Medium

题目描述

给你一个 n x n 的整数矩阵 board，棋盘上的方格按从 1 到 n² 编号，编号从棋盘左下角开始，每一行交替方向。

玩家从棋盘上的方格 1（总是在最后一行、第一列）开始出发。

每一回合，玩家需要从当前方格 curr 开始出发，按下述要求前进：

  • 选择目标方格 next，目标方格的编号符合范围 [curr + 1, min(curr + 6, n²)]。
    • 该选择模拟了掷骰子的情景，无论棋盘大小如何，玩家最多只能有 6 个目的地。
  • 如果目标方格 next 处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格 next。
  • 当玩家到达编号 n² 的方格时，游戏结束。

如果 board[r][c] != -1，位于 r 行 c 列的棋盘格中存在"蛇"或"梯子"；否则，该位置上没有"蛇"或"梯子"。

返回达到方格 n² 所需的最少掷骰子次数，如果不可能，则返回 -1。

示例 1：

输入：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]]
输出：4
解释：
首先，从方格 1 开始，你决定移动到方格 2。
你必须爬上梯子到方格 15。
然后你决定移动到方格 17。
你必须爬上蛇到方格 13。
然后你决定移动到方格 14。
你必须爬上梯子到方格 35。
然后你决定移动到方格 36，游戏结束。
可以证明你需要至少 4 次移动才能到达最后一个方格，所以答案是 4。

示例 2：

输入：board = [[-1,-1],[-1,3]]
输出：1

提示：

  • n == board.length == board[i].length
  • 2 <= n <= 20
  • board[i][j] 要么是 -1，要么在范围 [1, n²] 内
  • 编号为 1 和 n² 的方格上没有蛇或梯子

解题思路

这是一道典型的最短路径问题，可以使用 BFS（广度优先搜索） 求解。

解题思路：

  1. 棋盘映射：首先需要将棋盘上的编号映射到二维数组的行列坐标。由于棋盘是蛇形排列（奇偶行方向相反），需要特别处理坐标转换。

  2. BFS搜索：

    • 从方格1开始，使用队列存储当前位置和步数
    • 对于每个位置，尝试掷骰子（移动1-6步）
    • 如果目标方格有蛇或梯子，则传送到对应位置
    • 使用visited数组避免重复访问
    • 当到达第n²个方格时，返回步数

  3. 坐标转换函数：对于编号num，需要转换为(row, col)：

    • 行数：(num-1) // n，但要从底部开始，所以是n-1-(num-1)//n
    • 列数：如果行数为偶数（从底部开始计算），从左到右；如果为奇数，从右到左

算法优势： BFS保证找到的第一条路径就是最短路径，时间复杂度较优。

关键点：

  • 正确处理蛇形棋盘的坐标映射
  • 使用BFS确保最短路径
  • 避免重复访问已经到达过的方格

代码实现

class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int n = board.size();
        vector<bool> visited(n * n + 1, false);
        queue<pair<int, int>> q; // {position, steps}
        q.push({1, 0});
        visited[1] = true;
        
        while (!q.empty()) {
            auto [pos, steps] = q.front();
            q.pop();
            
            if (pos == n * n) return steps;
            
            for (int i = 1; i <= 6 && pos + i <= n * n; i++) {
                int next = pos + i;
                auto [r, c] = getCoordinate(next, n);
                
                if (board[r][c] != -1) {
                    next = board[r][c];
                }
                
                if (!visited[next]) {
                    visited[next] = true;
                    q.push({next, steps + 1});
                }
            }
        }
        
        return -1;
    }
    
private:
    pair<int, int> getCoordinate(int num, int n) {
        int row = (num - 1) / n;
        int col = (num - 1) % n;
        
        if (row % 2 == 1) {
            col = n - 1 - col;
        }
        
        return {n - 1 - row, col};
    }
};

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        visited = set()
        queue = deque([(1, 0)])  # (position, steps)
        visited.add(1)
        
        def get_coordinate(num):
            row = (num - 1) // n
            col = (num - 1) % n
            if row % 2 == 1:
                col = n - 1 - col
            return n - 1 - row, col
        
        while queue:
            pos, steps = queue.popleft()
            
            if pos == n * n:
                return steps
            
            for i in range(1, 7):
                if pos + i > n * n:
                    break
                    
                next_pos = pos + i
                r, c = get_coordinate(next_pos)
                
                if board[r][c] != -1:
                    next_pos = board[r][c]
                
                if next_pos not in visited:
                    visited.add(next_pos)
                    queue.append((next_pos, steps + 1))
        
        return -1

public class Solution {
    public int SnakesAndLadders(int[][] board) {
        int n = board.Length;
        bool[] visited = new bool[n * n + 1];
        Queue<(int pos, int steps)> queue = new Queue<(int, int)>();
        queue.Enqueue((1, 0));
        visited[1] = true;
        
        while (queue.Count > 0) {
            var (pos, steps) = queue.Dequeue();
            
            if (pos == n * n) return steps;
            
            for (int i = 1; i <= 6 && pos + i <= n * n; i++) {
                int next = pos + i;
                var (r, c) = GetCoordinate(next, n);
                
                if (board[r][c] != -1) {
                    next = board[r][c];
                }
                
                if (!visited[next]) {
                    visited[next] = true;
                    queue.Enqueue((next, steps + 1));
                }
            }
        }
        
        return -1;
    }
    
    private (int, int) GetCoordinate(int num, int n) {
        int row = (num - 1) / n;
        int col = (num - 1) % n;
        
        if (row % 2 == 1) {
            col = n - 1 - col;
        }
        
        return (n - 1 - row, col);
    }
}

var snakesAndLadders = function(board) {
    const n = board.length;
    const target = n * n;
    
    function getCoords(num) {
        const row = Math.floor((num - 1) / n);
        const col = (num - 1) % n;
        const actualRow = n - 1 - row;
        const actualCol = row % 2 === 0 ? col : n - 1 - col;
        return [actualRow, actualCol];
    }
    
    const queue = [[1, 0]];
    const visited = new Set([1]);
    
    while (queue.length > 0) {
        const [curr, moves] = queue.shift();
        
        if (curr === target) return moves;
        
        for (let next = curr + 1; next <= Math.min(curr + 6, target); next++) {
            if (visited.has(next)) continue;
            
            const [r, c] = getCoords(next);
            const destination = board[r][c] === -1 ? next : board[r][c];
            
            if (!visited.has(destination)) {
                visited.add(destination);
                queue.push([destination, moves + 1]);
            }
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²) - 每个方格最多访问一次，总共n²个方格
空间复杂度O(n²) - visited数组和队列的空间开销都是O(n²)

相关题目