05 August 2008
蛇梯棋
给你一个大小为 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。
最多有 20 * 2020∗20 个格子，直接使用常规的单向 BFS 进行求解即可。
为了方便我们可以按照题目给定的意思，将二维的矩阵「扁平化」为一维的矩阵，然后再按照规则进行 BFS。
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
35
36
37
38
39
40
41
42
43
44
class Solution {
int len;
int[] nums;
public int snakesAndLadders(int[][] board) {
len = board.length;
if (board[0][0] != -1) return -1;
nums = new int[len * len + 1];
boolean isRight = true;
for (int i = len - 1, index = 1; i >= 0; i--) {
for (int j = (isRight ? 0 : len - 1); isRight ? j < len : j >= 0; j += isRight ? 1 : -1) {
nums[index++] = board[i][j];
}
isRight = !isRight;
}
int result = bfs();
return result;
}
int bfs() {
Deque<Integer> deque = new ArrayDeque<>();
Map<Integer, Integer> map = new HashMap<>();
deque.addLast(1);
map.put(1, 0);
while (!deque.isEmpty()) {
int poll = deque.pollFirst();
int step = map.get(poll);
if (poll == len * len) return step;
for (int i = 1; i <= 6; i++) {
int np = poll + i;
if (np <= 0 || np > len * len) continue;
if (nums[np] != -1) {
np = nums[np];
}
if (map.containsKey(np)) {
continue;
}
map.put(np, step + 1);
deque.addLast(np);
}
}
return -1;
}
}