跳到主要内容

LeetCode 909. 蛇梯棋

本节目标

将蛇梯棋规则映射为隐式无权图，用分层 BFS 求最少掷骰次数。

这是图论综合的隐式状态图母题。棋盘格不需要预先列出边：从当前编号掷出 1..6 就生成至多六个下一状态。

查看 LeetCode 原题

题意与约束​

从编号 1 出发到编号 n²，每次掷骰可前进 1..6 格且不能越界。落到蛇或梯子所在格后最多传送一次；传送目标即使也标有蛇或梯子，也不能在同一次掷骰中继续传送。编号从棋盘底行开始，行方向交替。

直接思路与瓶颈​

枚举所有掷骰序列会随步数指数增长；即使记录“当前位置的最好步数”，若按普通矩阵坐标顺序推进，也难以保证先找到最少掷骰次数。每次掷骰成本都为一，状态图上的分层 BFS 正好按步数从小到大搜索。

图模型与算法推导​

把编号 1..n² 视为顶点。从 cur 掷出 die 得到落点 cur + die，经一次可能的传送后停在 nxt，这是一条单位权边。boardCell 把蛇形编号映射为数组坐标。队列保存传送后的编号；每层处理完才把步数加一，首次入队即标记访问。

正确性依据​

一次合法掷骰及其至多一次传送与一条生成边一一对应。BFS 按经过边数递增访问顶点，因此终点第一次被取出时的层数是最少掷骰次数。首次入队的状态已经由最短层到达，禁止再次入队不会丢失更短路径。

样例执行过程​

以 3 × 3 棋盘 [[-1,9,-1],[-1,-1,-1],[-1,8,-1]] 为例，编号范围为 1..9：格子 2 的梯子通向 8，格子 8 的梯子通向 9。第 0 层队列为 [1]；掷出 1 时先落到 2，本次只传送一次并停在 8，不能继续沿 8 -> 9 传送，其余点数产生 3..7，所以第 1 层队列为 [8,3,4,5,6,7]。处理 8 时掷出 1 到达 9，第 2 层取出终点并返回 2，与源码的分层 BFS 一致。

代码实现​

C++17
#include <queue>
#include <utility>
#include <vector>
using namespace std;

class Solution {
    pair<int, int> boardCell(int pos, int n) {
        int rowFromBottom = (pos - 1) / n;
        int col = (pos - 1) % n;
        if (rowFromBottom % 2 == 1) {
            col = n - 1 - col;
        }
        return {n - 1 - rowFromBottom, col};
    }

public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int n = static_cast<int>(board.size());
        int target = n * n;
        vector<bool> visited(target + 1, false);
        queue<int> pending;
        pending.push(1);
        visited[1] = true;

        int steps = 0;
        while (!pending.empty()) {
            int levelSize = static_cast<int>(pending.size());
            for (int i = 0; i < levelSize; i++) {
                int cur = pending.front();
                pending.pop();
                if (cur == target) {
                    return steps;
                }
                for (int die = 1; die <= 6 && cur + die <= target; die++) {
                    int nxt = cur + die;
                    auto [row, col] = boardCell(nxt, n);
                    if (board[row][col] != -1) {
                        nxt = board[row][col];
                    }
                    if (!visited[nxt]) {
                        visited[nxt] = true;
                        pending.push(nxt);
                    }
                }
            }
            steps++;
        }
        return -1;
    }
};

复杂度分析​

共有 n² 个格子，每格至多尝试六个骰子点数，时间 O(n²)；访问标记和队列最多存放 n² 个编号，空间 O(n²)。

边界与易错点​

  • 棋盘数组第 0 行在最上方，编号却从最下方开始。
  • 蛇形行的列方向必须交替。
  • 传送只检查一次，不能递归追踪下一个传送。
  • 必须在入队时标记访问，以免传送环重复扩张。

模式迁移​

游戏规则、自动跳转或操作序列只要每步成本相同，都可把“一次操作后的实际停点”建成一条边，再用分层 BFS 求最少操作数。