思路: BFS
这道题思路挺简单的。
每个被感染的设置被感染的时间，然后将其放到队列中。
已经被感染的就不要重复设置值了。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
int n, m, a, b;
pair<int, int> pr;
int dx[4] = { 0,-1,1,0 }, dy[4] = {-1,0,0,1};
int maps[maxn][maxn];
int main() {
cin >> n >> m >> a >> b;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
maps[i][j] = -1;
}
queue<pair<int, int>> qu;
for (int i = 0; i < a; i++) {
int x, y;
cin >> x >> y;
qu.push({ x,y });
maps[x][y] = 0;
}
int cnt = 0;
while (!qu.empty()) {
int ssize = qu.size();
cnt++;
for (int i = 0; i < ssize; i++) {
pair<int, int> cur = qu.front();
qu.pop();
for (int i = 0; i < 4; i++) {
int xx = cur.first + dx[i];
int yy = cur.second + dy[i];
if (maps[xx][yy]==-1 && xx > 0 && xx <= n && yy > 0 && yy <= m) {
maps[xx][yy] = cnt;//设置为已经被感染
qu.push({ xx,yy });
}
}
}
}
for (int i = 0; i < b; i++) {
int x, y;
cin >> x >> y;
cout << maps[x][y] << endl;
}
return 0;
}