蛇梯棋
难度:
标签:
题目描述
给你一个大小为 n x n 的整数矩阵 board ，方格按从 1 到 n2 编号，编号遵循 转行交替方式 ，从左下角开始 （即，从 board[n - 1][0] 开始）每一行交替方向。
玩家从棋盘上的方格 1 （总是在最后一行、第一列）开始出发。
每一回合，玩家需要从当前方格 curr 开始出发，按下述要求前进：
- 选定目标方格
next，目标方格的编号符合范围[curr + 1, min(curr + 6, n2)]。- 该选择模拟了掷 六面体骰子 的情景，无论棋盘大小如何，玩家最多只能有 6 个目的地。
- 传送玩家：如果目标方格
next处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格next。 - 当玩家到达编号
n2的方格时，游戏结束。
r 行 c 列的棋盘，按前述方法编号，棋盘格中可能存在 “蛇” 或 “梯子”；如果 board[r][c] != -1，那个蛇或梯子的目的地将会是 board[r][c]。编号为 1 和 n2 的方格上没有蛇或梯子。
注意，玩家在每回合的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，玩家也 不能 继续移动。
- 举个例子，假设棋盘是
[[-1,4],[-1,3]]，第一次移动，玩家的目标方格是2。那么这个玩家将会顺着梯子到达方格3，但 不能 顺着方格3上的梯子前往方格4。
返回达到编号为 n2 的方格所需的最少移动次数，如果不可能，则返回 -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 [第 5 行，第 0 列] 开始。 先决定移动到方格 2 ，并必须爬过梯子移动到到方格 15 。 然后决定移动到方格 17 [第 3 行，第 4 列]，必须爬过蛇到方格 13 。 接着决定移动到方格 14 ，且必须通过梯子移动到方格 35 。 最后决定移动到方格 36 , 游戏结束。 可以证明需要至少 4 次移动才能到达最后一个方格，所以答案是 4 。
示例 2：
输入：board = [[-1,-1],[-1,3]] 输出：1
提示：
n == board.length == board[i].length2 <= n <= 20grid[i][j]的值是-1或在范围[1, n2]内- 编号为
1和n2的方格上没有蛇或梯子
代码结果
运行时间: 36 ms, 内存: 16.8 MB
/*
* This solution uses Java Streams to implement the BFS algorithm to find the shortest path on the board.
* We still simulate dice rolls and handle snakes and ladders similarly to the previous solution.
* The use of streams makes the code more functional and concise.
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length;
boolean[] visited = new boolean[n * n + 1];
Queue<int[]> queue = new LinkedList<>(); // int[] contains {position, moves}
queue.add(new int[]{1, 0});
visited[1] = true;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int pos = current[0];
int moves = current[1];
if (pos == n * n) return moves;
IntStream.rangeClosed(1, 6)
.map(i -> pos + i)
.filter(nextPos -> nextPos <= n * n)
.mapToObj(nextPos -> {
int[] coordinates = getCoordinates(nextPos, n);
int row = coordinates[0], col = coordinates[1];
if (board[row][col] != -1) nextPos = board[row][col];
return new int[]{nextPos, moves + 1};
})
.filter(next -> !visited[next[0]])
.forEach(next -> {
visited[next[0]] = true;
queue.add(next);
});
}
return -1;
}
private int[] getCoordinates(int pos, int n) {
int row = n - 1 - (pos - 1) / n;
int col = (pos - 1) % n;
if ((n - row) % 2 == 0) col = n - 1 - col;
return new int[]{row, col};
}
}
解释
方法:
题解采用广度优先搜索（BFS）策略来解决蛇梯棋问题。首先，将棋盘转换成图的形式，使用字典存储蛇或梯子的映射。这个映射记录从当前位置可以直接到达的目标位置（如果有蛇或梯子的话）。随后使用BFS遍历所有可能的路径，寻找到达终点的最短路径。每一次投掷骰子，模拟1至6步的移动，检查每一个可能的目标位置，若有蛇或梯子，则直接跳转，否则移动到该格子。如果到达终点则立即返回所需的移动次数。若遍历完所有可能性都无法到达终点，则返回-1。
时间复杂度:
O(n^2)
空间复杂度:
O(n^2)
代码细节讲解
🦆
在BFS解决方案中，`graph`字典是如何准确映射蛇和梯子的目的地的？能否详细说明其构建过程？
▷🦆
为什么要选择广度优先搜索（BFS）而不是深度优先搜索（DFS）来解决这个问题？
▷🦆
题解中提到的优化，即记录未被蛇或梯子影响的最远移动（`max_norm_nxt`），在代码中似乎没有实际使用。这是故意为之还是存在遗漏？
▷🦆
在使用BFS时，为什么在遍历到终点时可以立即返回而不需要继续遍历其他可能的路径？
▷