前面问的"老鼠找奶酪" 算法题的js实现代码
时间: 2023-03-01 13:59:22 浏览: 62
这是一个迷宫问题,在一个二维矩阵中寻找从起点到终点的最短路径,其中矩阵中的障碍物需要被躲避。
下面是一个示例代码:
```
let grid = [
[1, 0, 1, 1, 1],
[1, 0, 1, 0, 1],
[1, 0, 1, 0, 1],
[1, 1, 1, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 0, 0, 0]
];
let start = [0, 0];
let end = [5, 4];
let bfs = function(grid, start, end) {
let queue = [];
queue.push(start);
let dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]];
let steps = 0;
while (queue.length > 0) {
let size = queue.length;
for (let i = 0; i < size; i++) {
let curr = queue.shift();
let x = curr[0];
let y = curr[1];
if (x === end[0] && y === end[1]) {
return steps;
}
for (let j = 0; j < dirs.length; j++) {
let dx = x + dirs[j][0];
let dy = y + dirs[j][1];
if (dx >= 0 && dx < grid.length && dy >= 0 && dy < grid[0].length && grid[dx][dy] === 0) {
queue.push([dx, dy]);
grid[dx][dy] = 1;
}
}
}
steps++;
}
return -1;
}
console.log(bfs(grid, start, end));
```