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
| class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length, boardSize = n * n;
boolean[] visited = new boolean[n * n + 1];
Deque<Integer> queue = new ArrayDeque<>();
visited[1] = true;
queue.offer(1);
int steps = 0;
while (!queue.isEmpty()) {
for (int i = queue.size(); i > 0; i--) {
int currLabel = queue.poll();
int rangeMax = Math.min(currLabel + 6, boardSize);
for (int j = currLabel + 1; j <= rangeMax; j++) {
int nextLabel = j;
int nextLabelRow = getRow(n, nextLabel), nextLabelCol = getCol(n, nextLabel);
if (board[nextLabelRow][nextLabelCol] != -1) {
nextLabel = board[nextLabelRow][nextLabelCol];
nextLabelRow = getRow(n, nextLabel);
nextLabelCol = getCol(n, nextLabel);
}
if (!visited[nextLabel]) {
if (nextLabel == boardSize) {
return steps + 1;
} else {
visited[nextLabel] = true;
queue.offer(nextLabel);
}
}
}
}
steps += 1;
}
return -1;
}
private int getRow(int n, int label) {
return (n - 1) - (label - 1) / n;
}
private int getCol(int n, int label) {
return ((label - 1) / n) % 2 == 0 ? (label - 1) % n : (n - 1) - (label - 1) % n;
}
}
|
BFS即可. 记得到达一个地方的时候要判断这里是不是snake or ladder, 如果是要把当前的位置更新为snake or ladder的destination.
时间复杂度: O(n * n)
空间复杂度: O(n * n)
