首页
登录 | 注册

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

相关文章

  • Windbg分析高内存占用问题
    1. 问题简介 最近产品发布大版本补丁更新,一商超客户升级后,反馈系统经常奔溃,导致超市的收银系统无法正常收银,现场排队付款的顾客更是抱怨声声.为了缓解现场的情况, 客户都是手动回收IIS应用程序池才能解决. 这样的后果是很严重的,接到反馈 ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.070 s.
京ICP备10005923号