130 lines
4.0 KiB
JavaScript
130 lines
4.0 KiB
JavaScript
/**
|
||
* @param {number[][]} board
|
||
* @return {number}
|
||
*/
|
||
const snakesAndLadders = function (board) {
|
||
|
||
};
|
||
|
||
/*
|
||
/*
|
||
把棋盘的每一个位置看成图的一个顶点，每一个顶点都有六个有向边指向后面的六个位置，也就是后面的六个顶点，有的顶点比较特殊，
|
||
它不指向后面的六个顶点，而是指向其他的顶点，我们要求的就是到达最后一个位置的顶点所需的最少步数，到这里我们很容易发现，这
|
||
是一个图的BFS题目，我们从最初的位置一层一层的往外扩，需要用几层就是几步，
|
||
*/
|
||
function f1(board) {
|
||
// 定义一个长度为n*n+1的一维数组，将board压缩，减少计数难度
|
||
const n = board.length;
|
||
const size = n * n;
|
||
const arr = new Array(size + 1); // 0位置不需要，这样就能和board一一对应
|
||
let idx = 1; // 棋盘初始位置
|
||
let leftToRight = true; // s行遍历board
|
||
|
||
for (let i = n - 1; i >= 0; i--) {
|
||
if (leftToRight) {
|
||
for (let j = 0; j < n; j++) {
|
||
arr[idx++] = board[i][j];
|
||
}
|
||
} else {
|
||
for (let j = n - 1; j >= 0; j--) {
|
||
arr[idx++] = board[i][j];
|
||
}
|
||
}
|
||
leftToRight = !leftToRight;
|
||
}
|
||
|
||
// bfs队列，从第一个位置开始，[1,0]表示，到达第一个位置最少只需要一步
|
||
const queue = [[1, 0]];
|
||
const visited = new Array(size + 1).fill(false); // 防止每一层的元素重复加入到下一层
|
||
visited[1] = true;
|
||
while (queue.length) {
|
||
const [cur, step] = queue.shift();
|
||
|
||
// 查看邻接的六个顶点
|
||
for (let i = 1; i <= 6; i++) {
|
||
let next = cur + i; // 下一个顶点位置
|
||
|
||
// 越界，忽略这个顶点
|
||
if (next > size) {
|
||
continue;
|
||
}
|
||
|
||
// 如果遇到蛇和梯子立即调整指定位置
|
||
if (arr[next] !== -1) {
|
||
next = arr[next];
|
||
}
|
||
|
||
// 如果邻接顶点就是目标位置，直接放回到达当前顶点的步数在加1
|
||
if (next === size) {
|
||
return step + 1;
|
||
}
|
||
|
||
// 如果元素没有被访问将其加入队列，扩展下一层
|
||
if (!visited[next]) {
|
||
visited[next] = true;
|
||
queue.push([next, step + 1]);
|
||
}
|
||
}
|
||
}
|
||
return -1; // 不可达
|
||
}
|
||
|
||
/*
|
||
将二维数组变成一维数组需要log(n*n)的时间复杂度，n为棋牌大小，相等于一开始就遍历了整个棋盘一遍，如果能实时计算当前位置，到其他位置
|
||
在board中的位置可以大大减少时间复杂度。
|
||
思考：假设我们有一个大小为n的棋牌，计数位置place(1 ~ n*n)在board中的坐标，首先计算行，行非常好计算，r = (place - 1) / n,那么列
|
||
还是 (place-1) % n吗？在这个题目不是的因为棋牌是按照s行走的，偶数行从左往右，奇数行从右往左，偶数行显然是(place-1)%n，那么技术行只需要将n
|
||
减去它即可
|
||
*/
|
||
|
||
const id2rc = (id, n) => {
|
||
const r = Math.floor((id - 1) / n);
|
||
let c = (id - 1) % n;
|
||
if (r % 2 === 1) {
|
||
c = n - 1 - c;
|
||
}
|
||
return [n - 1 - r, c];
|
||
};
|
||
|
||
function f2(board) {
|
||
const n = board.length;
|
||
const size = n * n;
|
||
|
||
// BFS
|
||
const queue = [[1, 0]];
|
||
const visited = new Array(size + 1).fill(false); // 防止每一层的元素重复加入到下一层
|
||
visited[1] = true;
|
||
|
||
while (queue.length) {
|
||
const [cur, step] = queue.shift();
|
||
|
||
// 查看邻接的六个顶点
|
||
for (let i = 1; i <= 6; i++) {
|
||
let next = cur + i; // 下一个顶点位置
|
||
|
||
// 越界，忽略这个顶点
|
||
if (next > size) {
|
||
continue;
|
||
}
|
||
|
||
const [r, c] = id2rc(next, n);
|
||
// 如果遇到蛇和梯子立即调整指定位置
|
||
if (board[r][c] !== -1) {
|
||
next = board[r][c];
|
||
}
|
||
|
||
// 如果邻接顶点就是目标位置，直接放回到达当前顶点的步数在加1
|
||
if (next === size) {
|
||
return step + 1;
|
||
}
|
||
|
||
// 如果元素没有被访问将其加入队列，扩展下一层
|
||
if (!visited[next]) {
|
||
visited[next] = true;
|
||
queue.push([next, step + 1]);
|
||
}
|
||
}
|
||
}
|
||
return -1; // 不可达
|
||
}
|