BFS：最短路径（无权图与网格）

一、面试常考点

1. 为什么 BFS 能求最短路

无权图每条边代价相同，按层扩展首次到达即最短。

2. 步数统计方式

按层循环，每层结束后步数 +1。

二、细节介绍

1. 网格 BFS

方向数组 + 越界判断 + 障碍判断。

2. 剪枝

已访问节点不重复入队。

三、示例代码

function shortestPathBinaryMatrix(grid) {
  const n = grid.length
  if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) return -1

  const dirs = [[1,0],[-1,0],[0,1],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1]]
  const queue = [[0, 0, 1]]
  grid[0][0] = 1

  while (queue.length) {
    const [x, y, d] = queue.shift()
    if (x === n - 1 && y === n - 1) return d

    for (const [dx, dy] of dirs) {
      const nx = x + dx
      const ny = y + dy
      if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue
      if (grid[nx][ny] !== 0) continue
      grid[nx][ny] = 1
      queue.push([nx, ny, d + 1])
    }
  }

  return -1
}

四、常用应用场景

1. 路由跳数

最少中转次数计算。

2. 迷宫类问题

最短步数寻路。