Javascript 算法 - 网格中线条笔画最少的路径

Question

我正在编写 javascript 代码，其中输入是网格、起始位置和目标位置。 f.e.

let grid = 

[
  [{ state: 'block' }, { state: 'block' }, { state: 'block' }, { state: 'block' }, { state: 'empty' }],
  
  [{ state: 'block' }, { state: 'empty' }, { state: 'empty' }, { state: 'empty' }, { state: 'block' }],
  
  [{ state: 'block' }, { state: 'empty' }, { state: 'empty' }, { state: 'empty' }, { state: 'empty' }],
  
  [{ state: 'empty' }, { state: 'block' }, { state: 'empty' }, { state: 'empty' }, { state: 'block' }],

  [{ state: 'empty' }, { state: 'empty' }, { state: 'block' }, { state: 'empty' }, { state: 'empty' }],

  [{ state: 'empty' }, { state: 'empty' }, { state: 'empty' }, { state: 'block' }, { state: 'empty' }],
];

let start = [1,1];

let end = [4,4];

我需要在开始和结束之间找到一条线条笔画最少的路径。在此示例中，它将是 [1,1] [1,2] [1,3] [2,3] [3,3] [4,3] [4,4]，因此只有三个线条笔画。我尝试了 bfs (https://codeburst.io/how-to-find-a-path-between-two-cells-in-a-grid-using-javascript-33fd01e3c66)，但它没有让我找到线条笔画数最少的路径。

Answer 1

我认为使用 BFS 的 Dijkstra 算法应该适用于此。

Answer 2

您可以使用典型的 BFS 图算法，但是当节点彼此相隔一个笔划时，节点被视为邻居。

这是一种编码方式：

function bfs(grid, start, end) {
    let comeFrom = new Map;
    comeFrom.set(grid[end[0], end[1]], null); // Mark start as visited
    let frontier = [start];
    while (frontier.length) {
        let nextFrontier = [];
        for (let node of frontier) {
            // For each of the 4 directions:
            for (let [dr, dc] of [[-1, 0], [0, -1], [1, 0], [0, 1]]) {
                let [r, c] = [node[0]+dr, node[1]+dc];
                // Continue in that same direction as far as possible
                while (grid[r]?.[c]?.state === "empty" && !comeFrom.has(grid[r][c])) {
                    // Register where we came from
                    comeFrom.set(grid[r][c], node);
                    if (r == end[0] && c == end[1]) { // found the target
                        // Construct the path from the comeFrom information
                        let path = [end];
                        while (r !== start[0] || c !== start[1]) {
                            [r, c] = comeFrom.get(grid[r][c]);
                            path.push([r, c]);
                        }
                        return path.reverse();
                    }
                    nextFrontier.push([r, c]);
                    r += dr;
                    c += dc;
                }
            }
        }
        // We did not find the target yet in this number of strokes. Consider one stroke more:
        frontier = nextFrontier;
    }
}

// Demo
let grid = [
    [{ state: 'block' }, { state: 'block' }, { state: 'block' }, { state: 'block' }, { state: 'empty' }],
    [{ state: 'block' }, { state: 'empty' }, { state: 'empty' }, { state: 'empty' }, { state: 'block' }],
    [{ state: 'block' }, { state: 'empty' }, { state: 'empty' }, { state: 'empty' }, { state: 'empty' }],
    [{ state: 'empty' }, { state: 'block' }, { state: 'empty' }, { state: 'empty' }, { state: 'block' }],
    [{ state: 'empty' }, { state: 'empty' }, { state: 'block' }, { state: 'empty' }, { state: 'empty' }],
    [{ state: 'empty' }, { state: 'empty' }, { state: 'empty' }, { state: 'block' }, { state: 'empty' }],
];
let start = [1, 1];
let end = [4,4];

let path = bfs(grid, start, end);
console.log(JSON.stringify(path));

该方案仅包括每个笔画的start/end个点，省略了笔画交叉的中间位置。它们可以从输出中扣除。

如果您希望明确包含它们，请将此视为一个练习。您需要在 while 循环中的 return 语句之前添加一个嵌套循环。

Javascript 算法 - 网格中线条笔画最少的路径

Javascript algorithm - path with fewest line strokes in grid

javascript

path-finding