题解

#include <bits/stdc++.h>
using namespace std;

/*
多源BFS，有多个起点
起点 = 感染源
*/
const int MAXA = 1E5 + 10, MAXN = 500 + 10, inf = 0x7f7f7f7f;

int g[MAXN][MAXN];
int n, m, a, b;
queue<pair<int,int>> q;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

void bfs() {
	// 所有起始状态已经进入队列，此处无需再次放入
	// BFS框架
	// 1. 取出队列首，进行四个方向的扩展
	// 2. 每次扩展前，判断是否可以扩展
	//  2.1 是否越界？是否重复感染？
	while (!q.empty()) {
		auto head = q.front();
		q.pop();
		
		int x = head.first, y = head.second;
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx > n || ny > m) continue; // 越界
			if (g[nx][ny] != inf) continue; // 已经被感染或者是感染源
			g[nx][ny] = g[x][y] + 1; // 队首元素感染时间 + 1 = 新感染者的感染时间
			q.push({nx, ny}); // 新感染者入队
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m >> a >> b;
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			g[i][j] = inf; // 初始化为无穷大，表示没有被感染，0表示感染源，其他数字表示感染时间
	
	for (int i = 1; i <= a; i++) {
		int x, y;
		cin >> x >> y;
		g[x][y] = 0;
		q.push({x, y});
	}
	
	bfs();
	
	for (int i = 1; i <= b; i++) {
		int x, y;
		cin >> x >> y;
		cout << g[x][y] << '\n';
	}
	
	return 0;
	
}