10-搜索/02-广度优先搜索

广度优先搜索（BFS）

BFS 从起点出发，逐层向外扩展。使用队列实现，保证第一次访问到的路径是最短路径（边权为 [math]\displaystyle{ 1 }[/math] 时）。

网格最短路

struct Node
{
    int x, y, step;
};

int bfs(int sx, int sy, int tx, int ty)
{
    queue<Node> q;
    q.push({sx, sy, 0});
    vis[sx][sy] = true;

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

    while (!q.empty())
    {
        auto [x, y, step] = q.front();
        q.pop();

        if (x == tx && y == ty)
            return step;

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (vis[nx][ny] || g[nx][ny] == '#') continue;
            vis[nx][ny] = true;
            q.push({nx, ny, step + 1});
        }
    }
    return -1; // 不可达
}

BFS 求最少步数

// 从 start 到 target 的最少变化次数
queue<string> q;
map<string, int> dist;

q.push(start);
dist[start] = 0;

while (!q.empty())
{
    string u = q.front();
    q.pop();

    if (u == target)
        return dist[u];

    for (string v : get_next(u))
    {
        if (!dist.count(v))
        {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

多源 BFS

将所有起点同时入队，即可求出到最近起点的距离：

queue<pair<int, int>> q;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (g[i][j] == 'S') // 所有起点入队
        {
            q.push({i, j});
            vis[i][j] = true;
            dis[i][j] = 0;
        }
// BFS 过程同上