题解 内存和时间复杂度超过>=80%用户

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
//666剧情——无需惊讶，你就是那个叛徒。在你的行踪败露之前，要尽快完成巫妖王交给你的任务。

const int MAX_N = 505;
const int MAX_B = 100005;

int dist[MAX_N][MAX_N];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

struct Point {
    int x, y;
    Point(int x_, int y_) : x(x_), y(y_) {}
};

int main() {
    int n, m, a, b;
    scanf("%d %d %d %d", &n, &m, &a, &b);

    // 初始化!!!
    memset(dist, -1, sizeof(dist));
    queue<Point> q;

    // 读取a个感染源，初始化队列和距离数组
    for (int i = 0; i < a; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        if (dist[x][y] == -1) { // 避免重复添加
            dist[x][y] = 0;
            q.push(Point(x, y));
        }
    }

    //!!! BFS扩散!!!
    while (!q.empty()) {
        Point p = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[p.x][p.y] + 1;
                q.push(Point(nx, ny));
            }
        }
    }

    // 读取领主坐标并查询
    int* lords_x = new int[MAX_B];
    int* lords_y = new int[MAX_B];
    for (int i = 0; i < b; ++i) {
        scanf("%d %d", &lords_x[i], &lords_y[i]);
    }

    for (int i = 0; i < b; ++i) {
        printf("%d\n", dist[lords_x[i]][lords_y[i]]);
    }

    delete[] lords_x;
    delete[] lords_y;

    return 0;
}

内存和时间复杂度超过>=80%用户