题意及思路

主要是讲先给出所有guard的位置，再给出所有incidents的位置，求出guard到达每个incident处最小的steps，其中guard每次可以向四周8个方向移动。

思路：对于每个guard使用bfs遍历它周围的点，算出相应的点到它的距离。

AC代码

#include
    
     using namespace std;int N, Q;struct Pla{    int x, y;};int dist[5000+10][5000+10];int dx[] = {-1, -1, -1, 1, 1, 1, 0, 0};int dy[] = {0, 1, -1, 0, 1, -1, 1, -1};queue
     
       q;void bfs(){    while(!q.empty())    {        Pla top = q.front();        q.pop();        for(int i = 0; i < 8; i++)        {            int curx = top.x + dx[i], cury = top.y + dy[i];            if(curx < 0 || curx > 5000 || cury < 0 || cury > 5000)      //先写这个会快些                continue;            if(dist[curx][cury] == -1)            {                Pla tmp = top;                tmp.x = curx, tmp.y = cury;                dist[curx][cury] = dist[top.x][top.y] + 1;                q.push(tmp);            }        }    }}int main(){//    freopen("input.txt", "r", stdin);//    freopen("output.txt", "w", stdout);    scanf("%d%d", &N, &Q);    memset(dist, -1, sizeof(dist));    while(!q.empty())        q.pop();    for(int i = 0; i < N; i++)    {        Pla guard;        scanf("%d%d", &guard.x, &guard.y);        dist[guard.x][guard.y] = 0;         //guard位置处都置为0        q.push(guard);              //将guard插入队列中，在后面进行bfs    }    bfs();    for(int i = 0; i < Q; i++)    {        int a, b;        scanf("%d%d", &a, &b);        printf("%d\n", dist[a][b]);    }}