图算法（Dijkstra / A*）实现最短路径与游戏寻路

// 运行环境：Node.js 14+
// 保存为 dsa-l25.js，执行：node dsa-l25.js

// 0=可走 1=障碍；返回从 (0,0) 到 (m-1,n-1) 的最短步数（Dijkstra/BFS）
function shortestPath(grid) {
  const m = grid.length, n = grid[0].length
  const dist = Array.from({ length: m }, () => new Array(n).fill(Infinity))
  dist[0][0] = 0
  const q = [[0, 0]]                       // 简单队列即可（边权=1）
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]]
  while (q.length) {
    const [x, y] = q.shift()
    for (const [dx, dy] of dirs) {
      const nx = x + dx, ny = y + dy
      if (nx<0||ny<0||nx>=m||ny>=n||grid[nx][ny]===1) continue
      if (dist[x][y] + 1 < dist[nx][ny]) { dist[nx][ny] = dist[x][y] + 1; q.push([nx, ny]) }
    }
  }
  return dist[m-1][n-1]
}

// A*：加曼哈顿距离启发式 h，用"f=g+h"最小优先（演示用数组代替堆）
function astar(grid) {
  const m = grid.length, n = grid[0].length
  const h = (x, y) => (m - 1 - x) + (n - 1 - y)   // 曼哈顿距离到终点
  const g = Array.from({ length: m }, () => new Array(n).fill(Infinity))
  g[0][0] = 0
  const open = [{ x: 0, y: 0, f: h(0, 0) }]
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]]
  while (open.length) {
    let bi = 0; for (let i = 1; i < open.length; i++) if (open[i].f < open[bi].f) bi = i
    const { x, y } = open.splice(bi, 1)[0]          // 取 f 最小
    if (x === m-1 && y === n-1) return g[x][y]
    for (const [dx, dy] of dirs) {
      const nx = x+dx, ny = y+dy
      if (nx<0||ny<0||nx>=m||ny>=n||grid[nx][ny]===1) continue
      const ng = g[x][y] + 1
      if (ng < g[nx][ny]) { g[nx][ny] = ng; open.push({ x: nx, y: ny, f: ng + h(nx, ny) }) }
    }
  }
  return Infinity
}

const map = [
  [0,0,0,0],
  [1,1,0,1],
  [0,0,0,0],
  [0,1,1,0],
]
console.log('Dijkstra/BFS 步数:', shortestPath(map)) // 8
console.log('A* 步数:', astar(map))                  // 8