【LeetCode每日一题】【BFS模版与例题】【二维数组】1293. 网格中的最短路径
var shortestPath = function (grid, k) {
let row = grid.length
let col = grid[0].length
// 特殊情况1：
if(row === 1 && col === 1) return 0
// 特殊情况2：最短的路径是row-1+col-1，在这条路径上最多有经过row+col-1个位置，除去起点、终点，最多可以有row+col-3个阻碍
if (k >= row + col - 3) {
return row + col - 2
}
let step = 0
let queue = [[0, 0, k]]
let visited = new Set()
visited.add(`${0},${0},${k}`)
while (queue.length) {
let size = queue.length
step++
for (let i = 0; i < size; i++) {
let [x, y, remainder] = queue.shift()
// 上下左右
const distance = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1]
]
// 遍历临近的节点
for (let j = 0; j < distance.length; j++) {
const [dx, dy] = distance[j]
let nextX = dx + x
let nextY = dy + y
if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col) {
continue
}
if (
grid[nextX][nextY] === 0 &&
!visited.has(`${nextX},${nextY},${remainder}`)
) {
// 满足条件时返回step
if (nextX === row - 1 && nextY === col - 1) {
return step
}
queue.push([nextX, nextY, remainder])
visited.add(`${nextX},${nextY},${remainder}`)
}
if (
grid[nextX][nextY] === 1 &&
remainder > 0 &&
!visited.has(`${nextX},${nextY},${remainder - 1}`)
) {
queue.push([nextX, nextY, remainder - 1])
visited.add(`${nextX},${nextY},${remainder - 1}`)
}
}
}
}
return -1
}