广度优先搜索

广度优先搜索（BFS）像水波一样“一层层往外扩”，用队列实现。在边权都为 $1$ 的无权图上，BFS 第一次到达某点时走的步数就是最短距离。

迷宫求最少步数：

queue<pair<int,int>> q;
q.push({sx, sy}); dist[sx][sy] = 0;
while (!q.empty()) {
    auto [x, y] = q.front(); q.pop();
    for (int i = 0; i < 4; i++) {
        int nx = x+dx[i], ny = y+dy[i];
        if (越界 || 是墙 || dist[nx][ny] != -1) continue;
        dist[nx][ny] = dist[x][y] + 1;   // 入队时就定下终值
        q.push({nx, ny});
    }
}

每个点入队、出队各一次，复杂度 $O(nm)$（图上则是 $O(V+E)$）。

坑：一是“标记已访问”要在入队时做，不能等出队才标，否则同一个点会被重复入队，退化甚至超时；二是 dist 初值设成 $-1$ 兼作“未访问”标记很方便；三是 BFS 只对无权图求最短路成立，带权图要用 Dijkstra，别搞混。