洛谷P1332血色先锋队笔记

完成代码：

#include <iostream>
using namespace std;
int map[505][505];//记录步数
int n, m, a, b, ax, ay, bx[100005], by[100005];//不要开太小
int f[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int queue[300005][2], head = 1, tail = 1;
bool check(int x, int y) {//检查是否越界
    if(x <= 0 || y <= 0 || x > n || y > m) {
        return false;
    }
    return true;
}
void bfs() {//十分普通的bfs
    while(head <= tail) {
        for(int i = 0; i < 4; i++) { 
            int xx, yy, num;
            num = map[queue[head][0]][queue[head][1]];//步数
            xx = queue[head][0] + f[i][0]; 
            yy = queue[head][1] + f[i][1];
            if(map[xx][yy] == 0 && check(xx, yy)) {//这里不需要去重的原因是先来的肯定更小
                queue[tail][0] = xx;
                queue[tail][1] = yy;
                tail++;
                map[xx][yy] = num + 1;
            }
        }
        head++;
    }
}
int main() {
    cin >> n >> m >> a >> b;
    for(int i = 1; i <= a; i++) {
        cin >> ax >> ay;
        map[ax][ay] = 1;//将起始点设置为1，因为若是0则会导致重复
        queue[tail][0] = ax;
        queue[tail][1] = ay;
        //上面两行是将所有起始点压入队列
        tail++;//tail注意在最后加
    }
    for(int i = 1; i <= b; i++) {
        cin >> bx[i] >> by[i];//输入领主的点
    }
    bfs();
    for(int i = 1; i <= b; i++) {
        cout << map[bx[i]][by[i]] - 1 << endl;//因为起始点+1,所有点需要-1
    }
    
    return 0;//好习惯
}

思路：直接将所有感染点压进去就完事了！

~OvO