以下是《【C++ BFS算法】909. 蛇梯棋 | 2019》题目的完整解析与讲解，适用于教学文章、视频讲解或代码注释脚本，强调 广度优先搜索（BFS） 的核心思想及其在解题中的应用。
🎲【C++ BFS算法】909. 蛇梯棋 | 2019题解通关指南
本题是 Leetcode 经典 BFS 模板题之一。掌握它，你将理解 BFS 如何解决最短路径问题 —— 哪怕是在一张扭曲的“蛇梯图”中！
📘 一、题目描述简述
给你一个 n x n 的蛇梯棋盘 board，你的目标是：
- 从方格
1出发 - 每次投掷一个六面骰子（即能前进 1～6 步）
- 走到
n x n方格，即最后一个格子
但棋盘上有蛇与梯子（即跳跃）：
- 如果你走到某格且该格为 -1，则正常停留；
- 如果不是 -1，则会强制跳到指定编号。
✅ 要求：
返回最少投掷几次骰子，才能到达终点。如果无法到达，返回 -1。
🧠 二、解题思路：广度优先搜索（BFS）
为什么用 BFS？
- 每一次骰子投掷都代表一次“状态转移”
- 我们要找的是“从 1 到终点的最短路径” → 典型 BFS 场景！
解题关键点：
- 一维映射：将 2D 棋盘坐标转换为 1D 编号
- 处理蛇梯跳跃：模拟跳跃行为
- BFS 队列推进：用队列维护当前位置和步数
- 避免重复访问：用 visited 数组
🧮 三、坐标映射技巧（蛇梯棋编号规则）
棋盘编号方式是“蛇形”，如下（以 n = 6 为例）：
36 35 34 33 32 31
25 26 27 28 29 30
24 23 22 21 20 19
13 14 15 16 17 18
12 11 10 9 8 7
1 2 3 4 5 6
➡️ 我们要把 编号转成坐标 (row, col)。
实现方式：
pair<int, int> getPos(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};
}
🧪 四、完整 C++ 解法（BFS 实现）
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
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; // {格子编号, 步数}
q.push({1, 0});
visited[1] = true;
while (!q.empty()) {
auto [curr, step] = q.front(); q.pop();
for (int i = 1; i <= 6; ++i) {
int next = curr + i;
if (next > n * n) break;
auto [r, c] = getPos(next, n);
if (board[r][c] != -1)
next = board[r][c]; // 蛇或梯子跳跃
if (next == n * n)
return step + 1;
if (!visited[next]) {
visited[next] = true;
q.push({next, step + 1});
}
}
}
return -1; // 无法到达
}
pair<int, int> getPos(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};
}
};
🧠 五、核心逻辑精讲
| 步骤 | 说明 |
|---|---|
| 队列初始化 | 从位置 1 开始，步数为 0 |
| 每轮展开 | 模拟骰子投掷（+1 到 +6） |
| 坐标转换 | 将编号映射为 (row, col) |
| 判断跳跃 | 若 board[row][col] != -1，则强制跳跃 |
| 终点判断 | 若跳到终点，立即返回步数 |
| 防止重复 | 标记 visited 防止死循环 |
🧱 六、复杂度分析
| 项目 | 分析 |
|---|---|
| 时间复杂度 | O(N²)，每个格子最多访问一次，BFS 最多扩展 6 个方向 |
| 空间复杂度 | O(N²)，visited 和队列空间 |
🎯 七、通关技巧 & 拓展思维
- 此题是 BFS 处理**“最少操作步数”**的典型代表
- 坐标映射技巧是解题关键
- 拓展题：棋盘 + 陷阱 或 多路径选择 的 BFS 都是类似套路
🧩 八、总结
| 你学到了什么？ |
|---|
| ✅ 如何在 BFS 中模拟骰子投掷 |
| ✅ 如何处理二维蛇形棋盘的坐标映射 |
| ✅ 如何结合 BFS 解决跳跃型路径最短问题 |
| ✅ 如何用 visited 阻止重复走格子 |
📚 推荐阅读（进阶）
- 🔗 [Leetcode 773. 滑动谜题]：同样是 BFS 求最短变换步数
- 🔗 [Leetcode 127. 单词接龙]：图上的最短路径模型
- 🔗 [手写 BFS 框架与套路归纳]（如需我可为你生成）
如果你希望我为这节内容配套生成讲解视频脚本、PPT 文件、动画可视化或更多 BFS 模板题讲解，欢迎继续提问！是否继续下一题或同类题目讲解？
发表回复