题意
从一些点向周围扩散,询问一个点上什么时候被扩散到。
思路
广搜模型。
代码
#include<queue>
#include<cstdio>
std::queue<std::pair<int, int> > q;
int n, m, a, b;
int map[501][501];
int check(int x, int y) {
return x > 0 && x <= n && y > 0 && y <= m;
}
void bfs() {
while (q.size()) {
int x = q.front().first, y = q.front().second;
q.pop();
if (map[x][y] == -1) map[x][y] = 0;
if (!map[x + 1][y] && check(x + 1, y)) map[x + 1][y] = map[x][y] + 1, q.push(std::make_pair(x + 1, y));
if (!map[x - 1][y] && check(x - 1, y)) map[x - 1][y] = map[x][y] + 1, q.push(std::make_pair(x - 1, y));
if (!map[x][y + 1] && check(x, y + 1)) map[x][y + 1] = map[x][y] + 1, q.push(std::make_pair(x, y + 1));
if (!map[x][y - 1] && check(x, y - 1)) map[x][y - 1] = map[x][y] + 1, q.push(std::make_pair(x, y - 1));
if (!map[x][y]) map[x][y] = -1;
}
}
int main() {
scanf("%d %d %d %d", &n, &m, &a, &b);
int x, y;
for (int i = 1; i <= a; i++)
scanf("%d %d", &x, &y), map[x][y] = -1, q.push(std::make_pair(x, y));
bfs();
for (int i = 1; i <= b; i++)
scanf("%d %d", &x, &y), printf("%d\n", map[x][y] != -1 ? map[x][y] : 0);
}