JavaScript: 使用 BFS 获取二进制矩阵中的最短路径

Question

我一直在使用 JavaScript 研究 leetcode，我正试图解决这个问题 https://leetcode.com/problems/shortest-path-in-binary-matrix/

这道题问的是return距离或者说最短路径的长度，我解决了。这是我的答案

var shortestPathBinaryMatrix = function(grid) {
    if(grid[0][0] != 0) return -1
    const queue = [[[0,0], 1]]
    const dest = [grid.length - 1, grid[0].length - 1]
    const visited = new Set()
    const getNextSteps = ([x,y]) => {
        const dirs = [[1, 0], [-1, 0] , [0,1], [0,-1], [1,1], [-1,1], [-1,-1], [1,-1]]
        const nextSteps = []
        for(const [nx, ny] of dirs) {
            if(grid[x + nx]?.[y + ny] == 0) nextSteps.push([x + nx, y + ny])
        }
        
        return nextSteps
    }
    
    for(const [curr, distance] of queue) {
        if(visited.has(curr.toString())) continue
        if(curr[0] === dest[0] && curr[1] === dest[1] && grid[dest[0]][dest[1]] == 0) return distance
        visited.add(curr.toString())
        getNextSteps(curr).forEach(adj => queue.push([adj, distance + 1]))
    }
    
    return -1
    
};

但是我想知道我是否也可以获得到达矩阵末尾所需的实际路径，所以我不想 return 将数字作为路径的长度，而是 return 实际路径，它是它在短路路径上访问的坐标数组。

比如输入的格子是[[0,0,0],[1,1,0],[1,1,0]]，就应该return[ [ 0, 0 ], [ 0, 1 ], [ 1, 2 ], [ 2, 2 ] ]

但做起来比看起来要难。我尝试了几种方法，但似乎无法解决。有人可以试试吗？

Answer 1

主要思想是使visited一个Map而不是一个Set，并注册为value访问路径上前一个节点的坐标节点。

为了实现这一点，我发现将访问标记设置为比您早一步更容易：在您将单元格放入队列时进行标记，而不是当您将其从队列中拉出。

到达目的地后，您可以将地图用作链表，然后沿着路径返回到源节点。这样你就可以重建路径。那么剩下的就是扭转它了。

这是您的代码，修改后标有注释：

var shortestPathBinaryMatrix = function(grid) {
    if(grid[0][0] != 0) return []; // modify return type
    const queue = [[[0,0], 1]];
    const dest = [grid.length - 1, grid[0].length - 1];
    const visited = new Map();
    visited.set([0,0].toString(), null); // Mark source as visited

    const getNextSteps = ([x,y]) => {
        const dirs = [[1, 0], [-1, 0] , [0,1], [0,-1], [1,1], [-1,1], [-1,-1], [1,-1]];
        const nextSteps = [];
        for(const [nx, ny] of dirs) {
            if(grid[x + nx]?.[y + ny] == 0) nextSteps.push([x + nx, y + ny]);
        }
        return nextSteps;
    }
    
    for (let [curr, distance] of queue) {
        // Move the visited check to the loop
        if (curr[0] === dest[0] && curr[1] === dest[1] && grid[dest[0]][dest[1]] == 0) {
            // Derive the path from the linked list we now have in the visited structure:
            let path = [];
            while (curr) {
                path.push(curr);
                curr = visited.get(curr.toString());
            }
            return path.reverse(); // Need to reverse to get from source to destination
        }
        for (let adj of getNextSteps(curr)) {
            // Visited-check moved here:
            if (visited.has(adj.toString())) continue; 
            // Mark with the coordinates of the previous node on the path:
            visited.set(adj.toString(), curr);
            queue.push([adj, distance + 1]);
        }
    }
    
    return []; // must modify this as well
};

// demo
let grid = [[0,0,0],[1,1,0],[1,1,0]];
let result = shortestPathBinaryMatrix(grid);
console.log(result);

无关：养成用分号结束语句的习惯是很好的。让你的代码依赖于 automatic semi-colon insertion algorithm 当然是可能的，但你不会是第一个落入它所拥有的晦涩陷阱之一的人。

JavaScript: 使用 BFS 获取二进制矩阵中的最短路径

JavaScript: get shortest path in binary matrix using BFS

javascript

algorithm

graph

breadth-first-search