多源BFS

过了这题的代码应该有两种：

1.分别从出口BFS, 找出所有的出口到各个点的最短路

2.多源BFS

首先说一下第一种做法，慢慢过渡到多源BFS.

每次BFS的复杂度都是$O(n\ast m)O(n*m)$，对于每个$pok{e}^{\mathrm{ˊ}}manpoke^ˊman$，如果我们每次都从对应入口BFS找距离最短的出口，那么时间复杂度最坏是$O(1e5\ast 1e3\ast 1e3)O(1e5*1e3*1e3)$, 铁TLE。

而从出口BFS, 处理出到每个位置的最短距离, 在每次询问时$O(1)O(1)$查询, 时间复杂度是$O(10\ast N\ast M)O(10*N*M)$, 最坏也就是$O(10\ast 1e3\ast 1e3)O(10*1e3*1e3)$。

简单来说,就是暴力地从每个出口分别BFS一次, 最多BFS十次。

暴力BFS的代码

#include<bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
using ll = long long;
const int N  =  1010;
int g[N][N], d[N][N], st[N][N];
int n, m, k, t, p;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
void  bfs(int x, int y)
{
    memset(st, false, sizeof st);
    queue<PII> q;
    q.push({x, y});
    st[x][y] = true;
    d[x][y] = 0;
    while(!q.empty()) {
        auto tt = q.front();
        q.pop();
        for(int i = 0;i < 4;i++) {
            int xx = tt.first + dx[i], yy = tt.second + dy[i];
            if (st[xx][yy] || g[xx][yy] != 0) continue;
            if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
            d[xx][yy] = min(d[xx][yy], d[tt.first][tt.second] + 1);
            st[xx][yy] = true;
            q.push({xx, yy});
        }
    }
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    memset(d, 0x3f, sizeof d);
    cin >> n >> m >> k;
    for(int i = 0;i < k;i++){
    	int x, y; cin >> x >> y;
        g[x][y] = -1;
    }
    cin >> t;
    for(int i = 0;i < t;i++ ) {
    	int x, y; cin >> x >> y;
        g[x][y] = 1;
        bfs(x, y);
    }
    cin >> p;
    for(int i = 0;i < p;i++) {
        int x, y; cin >> x >> y;
        if(d[x][y] == 0x3f3f3f3f) d[x][y] = -1;
        cout << d[x][y] << '\n';
    }
    return 0;
}

.

如果我们建立一个虚拟的超级源点，使其到所有出口的距离为$00$，就只需要BFS一次。

建立超级源点/汇点是图论中一个常用的技巧，在不同算法中有不同的实现方式, BFS时并不需要指定一个节点作为超级源点，只需要把超级源点可以到达的节点直接加入队列，然后BFS即可。

这是因为BFS时，队列中仅有两种节点，即到超级源点所在节点的距离为$distdist$的点和到超级源点所在节点的距离为$dist+1dist\; +\; 1$的点。因此，建立虚拟源点之后，所有的出口在队列中都属于同一类节点。

显然建立超级源点是一种更优也更通用的解法，如果本题数据范围变为，暴力BFS十次的做法就会被卡掉。

多源BFS的代码

#include<bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
using ll = long long;
const int N  =  1010;
int g[N][N], d[N][N], st[N][N];
int n, m, k, t, p;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

queue<PII> q;
void  bfs()
{
    while(!q.empty()) {
        auto tt = q.front();
        q.pop();
        for(int i = 0;i < 4;i++) {
            int xx = tt.first + dx[i], yy = tt.second + dy[i];
            if (st[xx][yy] || g[xx][yy] == -1) continue;
            if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
            d[xx][yy] = d[tt.first][tt.second] + 1;
            st[xx][yy] = 1;
            q.push({xx, yy});
        }
    }
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    memset(d, 0x3f, sizeof d);
    cin >> n >> m >> k;
    for(int i = 0;i < k;i++){
    	int x, y; cin >> x >> y;
        g[x][y] = -1;
    }
    cin >> t;
    for(int i = 0;i < t;i++ ) {
    	int x, y; cin >> x >> y;
    	q.push({x, y});
    	st[x][y] = 1;
    	d[x][y] = 0;
    }
    bfs();
    cin >> p;
    for(int i = 0;i < p;i++) {
        int x, y; cin >> x >> y;
        if(d[x][y] == 0x3f3f3f3f) d[x][y] = -1;
        cout << d[x][y] << '\n';
    }
    return 0;
}