多源BFS

介绍

1. 基本作用：求若干个起点到若干个终点的最短距离（路径）
2. 基本方法：BFS、添加一个虚拟原点（虚拟原点到起点的边权为0）
3. 适用题目：边权为正且都相同；求若干起点到终点的最短距离（路径） PS：只保留一个最短的.

代码思路

整体思路：
    假设有一个虚拟原点，虚拟原点到若干起点的边权为0
    这样我们可以将原模型转化为单源BFS
    也就是虚拟原点到若干终点的距离（由于边权为0，所以答案并不会改变）
    我们首先设置起点的距离为0（beacuse：虚拟原点到若干起点的边权为0）
    再将它们放入队列中
    最后用单源BFS求最短路的方法即可

代码思路：
1. 在BFS函数之前初始化数组
2. 遍历地图，找到若干起点
3. 将起点坐标放入队列并设置距离为0
4. 最后像单源BFS一样做就可以了

题目应用

173. 矩阵距离（算法提高课）

173. 矩阵距离

思路：

将多源BFS通过初始化距离数组与队列转化为单源BFS。

代码：

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int n, m;
char g[N][N];
int dist[N][N];
queue<PII> q;

void bfs()
{
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    while(q.size())
    {
        PII tmp = q.front();
        q.pop();

        for(int i = 0; i < 4; i++)
        {
            int nx = tmp.x + dx[i], ny = tmp.y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(dist[nx][ny] != -1) continue;

            q.push({nx, ny});
            dist[nx][ny] = dist[tmp.x][tmp.y] + 1;
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> g[i];

    memset(dist, -1, sizeof dist);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(g[i][j] == '1')
            {
                dist[i][j] = 0;
                q.push({i, j});
            }

    bfs();

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
            cout << dist[i][j] << " ";

        cout << endl;
    }

    return 0;
}