世界的尽头

宽度优先搜索

宽度优先搜索（Breadth-First Search，BFS）会从起点出发，按照距离由近到远的顺序逐层扩展状态：

距离 0：起点
距离 1：一步能够到达的点
距离 2：两步能够到达的点
……

BFS 使用队列维护待扩展的状态。队列先进先出的性质保证距离较小的点总是先被处理，因此它适合求解每条边代价相同的最短路问题。

网格图建模

在迷宫问题中，可以把每个可以行走的格子看成一个节点。如果两个格子上下或左右相邻，并且都可以行走，就在它们之间连一条长度为 $1$ 的边。

对于位置 $(x,y)$ ，四个相邻位置可以使用方向数组统一枚举：

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

第 i 个方向对应的新位置为：

int next_x = x + dx[i];
int next_y = y + dy[i];

每次移动的代价都是 $1$ ，因此迷宫可以看成一张无权图，起点到终点的最少移动次数就是这张图上的最短路长度。

BFS 模板

使用 dist[x][y] 表示起点到格子 $(x,y)$ 的最短距离：

dist[x][y] == -1：该格子尚未访问；
dist[x][y] >= 0：该格子已经访问，其值为起点到该格子的最短距离。

int bfs() {
  memset(dist, -1, sizeof dist);
 
  queue<pair<int, int>> q;
  q.push({0, 0});
  dist[0][0] = 0;
 
  while (!q.empty()) {
    auto current = q.front();
    q.pop();
 
    for (int i = 0; i < 4; i++) {
      int x = current.first + dx[i];
      int y = current.second + dy[i];
 
      if (x >= 0 && x < n && y >= 0 && y < m &&
          grid[x][y] == 0 && dist[x][y] == -1) {
        dist[x][y] =
            dist[current.first][current.second] + 1;
        q.push({x, y});
      }
    }
  }
 
  return dist[n - 1][m - 1];
}

一个格子第一次被发现时就立即记录距离并入队。这样既能确定其最短距离，又能把 dist 数组同时作为访问标记，保证每个格子最多入队一次。

正确性说明

下面证明 BFS 得到的 dist[x][y] 是起点到每个可达格子的最短距离。

BFS 的起点距离为 $0$ ，显然正确。假设队列中所有距离不超过 $k$ 的格子，其距离都已经正确计算。处理一个距离为 $k$ 的格子时，从它出发可以用一步到达尚未访问的相邻格子，因此为这些格子记录的距离是 $k+1$ 。

如果某个相邻格子存在小于 $k+1$ 的路径，那么它应该由距离小于 $k$ 的前驱更早发现，与“当前仍未访问”矛盾。因此，该格子第一次被发现时得到的 $k+1$ 就是最短距离。

由归纳法可知，BFS 为所有可达格子记录的都是最短距离，最终返回的 dist[n - 1][m - 1] 就是起点到终点的最少移动次数。

AcWing 844：走迷宫

题意

给定一个 $n \times m$ 的整数矩阵：

0 表示可以行走的格子；
1 表示障碍物。

从左上角 $(0,0)$ 出发，每次可以向上、下、左、右移动一个格子，求走到右下角 $(n-1,m-1)$ 的最少移动次数。

题目保证左上角和右下角都是 0，并且一定存在一条从起点到终点的路径。

思路

从 $(0,0)$ 开始执行 BFS。每次取出队首格子，枚举它的四个相邻位置。一个位置只有同时满足以下条件时才能入队：

没有越过矩阵边界；
不是障碍物；
之前没有访问过。

设当前格子为 $(x,y)$ ，相邻格子为 $(a,b)$ ，则第一次到达相邻格子时：

\operatorname{dist}[a][b] = \operatorname{dist}[x][y]+1.

完整代码

#include <cstring>
#include <iostream>
#include <queue>
#include <utility>
 
using namespace std;
 
const int N = 1010;
 
using PII = pair<int, int>;
 
int n, m;
int grid[N][N];
int dist[N][N];
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int bfs() {
  memset(dist, -1, sizeof dist);
 
  queue<PII> q;
  q.push({0, 0});
  dist[0][0] = 0;
 
  while (!q.empty()) {
    PII current = q.front();
    q.pop();
 
    for (int i = 0; i < 4; i++) {
      int x = current.first + dx[i];
      int y = current.second + dy[i];
 
      if (x >= 0 && x < n && y >= 0 && y < m &&
          grid[x][y] == 0 && dist[x][y] == -1) {
        dist[x][y] =
            dist[current.first][current.second] + 1;
        q.push({x, y});
      }
    }
  }
 
  return dist[n - 1][m - 1];
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  cin >> n >> m;
 
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> grid[i][j];
    }
  }
 
  cout << bfs() << '\n';
 
  return 0;
}

样例

输入：

输出：

一条最短路径为：

(0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2)
       -> (2,3) -> (2,4) -> (3,4) -> (4,4)

共移动 $8$ 次。

复杂度分析

矩阵中共有 $n \times m$ 个格子。每个格子最多入队一次，出队后只枚举四个方向，因此：

时间复杂度为 $O(nm)$ ；
dist 数组和队列最多保存 $O(nm)$ 个状态，额外空间复杂度为 $O(nm)$ 。

常见错误

先入队，后标记访问：同一个格子可能被多个相邻格子重复加入队列。应该在第一次发现格子、把它加入队列时立即更新 dist。
没有初始化距离数组：全局数组默认值为 0，不能区分起点和未访问格子。应先使用 memset(dist, -1, sizeof dist)。
边界条件写错：合法坐标应满足 0 <= x < n 且 0 <= y < m。
混淆行列范围：行坐标与 n 比较，列坐标与 m 比较。
把障碍物加入队列：只有 grid[x][y] == 0 的格子可以行走。
使用 DFS 求最短路：普通 DFS 会先沿一条路径走到底，不能直接保证第一次到达终点时路径最短；单位边权最短路应优先使用 BFS。
重复调用时复用全局队列：把队列定义在 bfs() 内部，可以保证每次调用都从空队列开始。
把经过格子数当作移动次数：起点距离是 0，每经过一条边距离增加 1。

1-走迷宫