力扣每日一题——蛇梯棋-海口c网

力扣每日一题——蛇梯棋

article/2025/7/19 21:21:05

题目链接：909. 蛇梯棋 - 力扣（LeetCode）

题目描述

解法一：BFS+坐标转换

Java写法：

C++写法：

运行时间

时间复杂度和空间复杂度

总结

题目链接：909. 蛇梯棋 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

给你一个大小为 n x n 的整数矩阵 board ，方格按从 1 到 n2 编号，编号遵循转行交替方式，从左下角开始 （即，从 board[n - 1][0] 开始）的每一行改变方向。

你一开始位于棋盘上的方格 1。每一回合，玩家需要从当前方格 curr 开始出发，按下述要求前进：

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

如果 board[r][c] != -1 ，位于 r 行 c 列的棋盘格中可能存在 “蛇” 或 “梯子”。那个蛇或梯子的目的地将会是 board[r][c]。编号为 1 和 n2 的方格不是任何蛇或梯子的起点。

注意，玩家在每次掷骰的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，玩家也不能继续移动。

举个例子，假设棋盘是 [[-1,4],[-1,3]] ，第一次移动，玩家的目标方格是 2 。那么这个玩家将会顺着梯子到达方格 3 ，但不能顺着方格 3 上的梯子前往方格 4 。（简单来说，类似飞行棋，玩家掷出骰子点数后移动对应格数，遇到单向的路径（即梯子或蛇）可以直接跳到路径的终点，但如果多个路径首尾相连，也不能连续跳多个路径）

返回达到编号为 n2 的方格所需的最少掷骰次数，如果不可能，则返回 -1。

解法一：BFS+坐标转换

棋盘布局和移动规则是关键起点
棋盘编号从左下角（1号）开始蛇形迂回，最后一行从左到右，倒数第二行从右到左，交替上升。每次移动相当于掷骰子（1-6步），落到普通格子（值为-1）就停下；若落点有梯子或蛇（值非-1），则立刻传送到对应编号的格子，但只能传送一次——即便新位置又有梯子也不会二次触发。比如落到2号格子若标着15，会直接跳到15，但不会接着触发15号格的传送。

BFS是解题的核心武器
因为每次掷骰算一步，BFS能天然保证最先到达终点的路径步数最少。执行流程：从起点1（步数0）开始，用队列记录当前位置和步数，同时用visited数组避免重复访问。每一步从队列取出当前格子，模拟掷1~6点骰子，计算下一步编号。如果下一步有梯子/蛇，则更新位置到其目标值；如果直达终点（n²号），返回当前步数+1；否则将未访问的位置加入队列。

坐标转换是最大难点
二维数组的行列索引和棋盘编号的映射容易出错：

实际行号（从底部计）：real_row = (编号 - 1) / n
数组行索引（从顶部计）：array_row = n - 1 - real_row
列索引：由real_row的奇偶决定方向——偶数行（0,2,4...）从左到右：col = (编号 - 1) % n；奇数行（1,3,5...）从右到左：col = n - 1 - (编号 - 1) % n。
例如6x6棋盘中，编号10的real_row=1（奇数行），列需从右向左计算。

边界和易错点需警惕
移动后编号超过n²要跳过；起点（1号）和终点（n²号）保证无梯子/蛇；visited数组防循环（如两个传送门互跳）；测试时注意坐标转换是否正确——比如棋盘左上角（编号21）若有梯子board[0][0]=2，若坐标算错会漏传送。

本质上，这是带传送机制的迷宫最短路径问题，BFS配合坐标转换的细心处理即可高效破解。

Java写法：

import java.util.*;class Solution {public int snakesAndLadders(int[][] board) {int n = board.length;int max = n * n;boolean[] visited = new boolean[max + 1];Queue<int[]> queue = new LinkedList<>();queue.offer(new int[]{1, 0});visited[1] = true;while (!queue.isEmpty()) {int[] curr = queue.poll();int pos = curr[0], steps = curr[1];if (pos == max) return steps;for (int i = 1; i <= 6; i++) {int next = pos + i;if (next > max) break;// 修正坐标转换int real_row = (next - 1) / n;int array_row = n - 1 - real_row;int col = (real_row % 2 == 0) ? (next - 1) % n : n - 1 - (next - 1) % n;// 检查传送if (board[array_row][col] != -1) {next = board[array_row][col];}if (!visited[next]) {visited[next] = true;queue.offer(new int[]{next, steps + 1});}}}return -1;}
}

C++写法：

#include <vector>
#include <queue>
using namespace std;class Solution {
public:int snakesAndLadders(vector<vector<int>>& board) {int n = board.size();int max = n * n;vector<bool> visited(max + 1, false);queue<pair<int, int>> q; // <位置, 步数>q.push({1, 0});visited[1] = true;while (!q.empty()) {auto [pos, steps] = q.front();q.pop();if (pos == max) return steps;for (int i = 1; i <= 6; i++) {int next = pos + i;if (next > max) break;// 修正坐标转换int real_row = (next - 1) / n;int array_row = n - 1 - real_row;int col = (real_row % 2 == 0) ? (next - 1) % n : n - 1 - (next - 1) % n;// 检查传送if (board[array_row][col] != -1) {next = board[array_row][col];}if (!visited[next]) {visited[next] = true;q.push({next, steps + 1});}}}return -1;}
};