-
Notifications
You must be signed in to change notification settings - Fork 0
/
1091. 二进制矩阵中的最短路径-MEDIUM.js
46 lines (44 loc) · 1.07 KB
/
1091. 二进制矩阵中的最短路径-MEDIUM.js
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
45
46
// https://leetcode.cn/problems/shortest-path-in-binary-matrix/
/**
* @param {number[][]} grid
* @return {number}
*/
const paramGrid = [
[0, 0, 0],
[1, 1, 0],
[1, 1, 0]
];
/**
*
*/
var shortestPathBinaryMatrix = function (grid) {
if (grid[0][0] === 1) {
return -1;
}
const len = grid.length;
let dist = new Array(len).fill('').map(() => new Array(len).fill(Infinity));
dist[0][0] = 1;
let temp = [[0, 0]];
while (temp.length > 0) {
const [x, y] = temp.shift();
for (let dx = -1; dx <= 1; dx++) {
for (let dy = -1; dy <= 1; dy++) {
if (x == len - 1 && y == len - 1) {
return dist[x][y];
}
// 边界情况
if (x + dx < 0 || x + dx >= len || y + dy < 0 || y + dy >= len) {
continue;
}
// 被访问了
if (grid[x + dx][y + dy] > 0 || dist[x + dx][y + dy] <= dist[x][y] + 1) {
continue;
}
dist[x + dx][y + dy] = dist[x][y] + 1;
temp.push([x + dx, y + dy]);
}
}
}
return -1;
};
console.log(shortestPathBinaryMatrix(paramGrid));