Security Guards (Gym - 101954B)( bfs + 打表 )
2024-09-01 03:30:19
题意及思路
题目主要是讲先给出所有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]);
}
}
最新文章
- chrome 更新flash插件
- OpenStack 架构 - 每天5分钟玩转 OpenStack(15)
- QC学习一:Windows环境中Quality Center 9.0安装详解
- Leetcode 130. Surrounded Regions
- iOS 在类别里添加成员变量的方法:objc_setAssociatedObject
- oracle11g安装和基本的使用-转载
- ASP.NET MVC Validation
- 解决spring-mvc @responseBody注解返回json 乱码问题
- Hadoop修改SSH端口号
- iOS另类的内存管理
- ios固定高度禁止惯性滚动
- linux查看端口占用
- 为什么总是要求使用position的时候父类是relative
- Reason的介绍和搭建Reason开发环境
- leveldb(ssdb)性能、使用场景评估
- robotframework 远程连接数据库问题
- Mac OS X10.8.3-bash基本命令失效后的修复
- 【python】python之tuple元组
- 《Linux内核分析》课程第四周学习总结
- shell脚本批量部署ssh