题目描述
给你一个大小为 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。
示例 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 <= 20board[i][j] 的值是 -1 或在范围 [1, n2] 内- 编号为
1 和 n2 的方格上没有蛇或梯子
解法
方法一：BFS
我们可以使用广度优先搜索的方法，从起点开始，每次向前走 1 到 6 步，然后判断是否有蛇或梯子，如果有，就走到蛇或梯子的目的地，否则就走到下一个方格。
具体地，我们使用一个队列 $\textit{q}$ 来存储当前可以到达的方格编号，初始时将编号 $1$ 放入队列。同时我们使用一个集合 $\textit{vis}$ 来记录已经到达过的方格，避免重复访问，初始时将编号 $1$ 加入集合 $\textit{vis}$。
在每一次的操作中，我们取出队首的方格编号 $x$，如果 $x$ 是终点，那么我们就可以返回当前的步数。否则我们将 $x$ 向前走 $1$ 到 $6$ 步，设新的编号为 $y$，如果 $y$ 落在棋盘外，那么我们就直接跳过。否则，我们需要找到 $y$ 对应的行和列，由于行的编号是从下到上递减的，而列的编号与行的奇偶性有关，因此我们需要进行一些计算得到 $y$ 对应的行和列。
如果 $y$ 对应的方格上有蛇或梯子，那么我们需要额外走到蛇或梯子的目的地，设其为 $z$。如果 $z$ 没有被访问过，我们就将 $z$ 加入队列和集合中，这样我们就可以继续进行广度优先搜索。
如果我们最终无法到达终点，那么我们就返回 $-1$。
时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。其中 $n$ 是棋盘的边长。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
n = len(board)
q = deque([1])
vis = {1}
ans = 0
m = n * n
while q:
for _ in range(len(q)):
x = q.popleft()
if x == m:
return ans
for y in range(x + 1, min(x + 6, m) + 1):
i, j = divmod(y - 1, n)
if i & 1:
j = n - j - 1
i = n - i - 1
z = y if board[i][j] == -1 else board[i][j]
if z not in vis:
vis.add(z)
q.append(z)
ans += 1
return -1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length;
Deque<Integer> q = new ArrayDeque<>();
q.offer(1);
int m = n * n;
boolean[] vis = new boolean[m + 1];
vis[1] = true;
for (int ans = 0; !q.isEmpty(); ++ans) {
for (int k = q.size(); k > 0; --k) {
int x = q.poll();
if (x == m) {
return ans;
}
for (int y = x + 1; y <= Math.min(x + 6, m); ++y) {
int i = (y - 1) / n, j = (y - 1) % n;
if (i % 2 == 1) {
j = n - j - 1;
}
i = n - i - 1;
int z = board[i][j] == -1 ? y : board[i][j];
if (!vis[z]) {
vis[z] = true;
q.offer(z);
}
}
}
}
return -1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | class Solution {
public:
int snakesAndLadders(vector<vector<int>>& board) {
int n = board.size();
queue<int> q{{1}};
int m = n * n;
vector<bool> vis(m + 1);
vis[1] = true;
for (int ans = 0; !q.empty(); ++ans) {
for (int k = q.size(); k > 0; --k) {
int x = q.front();
q.pop();
if (x == m) {
return ans;
}
for (int y = x + 1; y <= min(x + 6, m); ++y) {
int i = (y - 1) / n, j = (y - 1) % n;
if (i % 2 == 1) {
j = n - j - 1;
}
i = n - i - 1;
int z = board[i][j] == -1 ? y : board[i][j];
if (!vis[z]) {
vis[z] = true;
q.push(z);
}
}
}
}
return -1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | func snakesAndLadders(board [][]int) int {
n := len(board)
q := []int{1}
m := n * n
vis := make([]bool, m+1)
vis[1] = true
for ans := 0; len(q) > 0; ans++ {
for k := len(q); k > 0; k-- {
x := q[0]
q = q[1:]
if x == m {
return ans
}
for y := x + 1; y <= min(x+6, m); y++ {
i, j := (y-1)/n, (y-1)%n
if i%2 == 1 {
j = n - j - 1
}
i = n - i - 1
z := y
if board[i][j] != -1 {
z = board[i][j]
}
if !vis[z] {
vis[z] = true
q = append(q, z)
}
}
}
}
return -1
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | function snakesAndLadders(board: number[][]): number {
const n = board.length;
const q: number[] = [1];
const m = n * n;
const vis: boolean[] = Array(m + 1).fill(false);
vis[1] = true;
for (let ans = 0; q.length > 0; ans++) {
const nq: number[] = [];
for (const x of q) {
if (x === m) {
return ans;
}
for (let y = x + 1; y <= Math.min(x + 6, m); y++) {
let i = Math.floor((y - 1) / n);
let j = (y - 1) % n;
if (i % 2 === 1) {
j = n - j - 1;
}
i = n - i - 1;
const z = board[i][j] === -1 ? y : board[i][j];
if (!vis[z]) {
vis[z] = true;
nq.push(z);
}
}
}
q.length = 0;
for (const x of nq) {
q.push(x);
}
}
return -1;
}
|