Security Guards （Gym - 101954B）（ bfs + 打表 ）

题意及思路

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

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

AC代码

#include<bits/stdc++.h>

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<Pla> 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]);

    }

}