网赛的时候看了这道题,发现就是平常的那种基础搜索题。
由于加了一个特殊条件:可以一次消耗3秒或原地停留1秒。
那就不能使用简单的队列了,需要使用优先队列才行。
题意
告诉一副地图:一个起点,一个终点,若干墙,若干监视器,剩下的是空地。
起点,终点,监视器都算空地。
监视器初始值会指定一个方向,共有四个方向。
监视器每秒顺时针转动到下个方向。
监视器视野距离为2.
在监视器的位置或在监视器面向的格子是监视区域。
普通的移动一格需要消耗1秒时间。
在监视器下移动一格需要消耗3秒时间。
如果呆在原地不动,即使在监视器视野内也不会被发现。
求最少时间从起点到达终点。
不能到达输出-1。
思路
第一步显然是先算算是不是可以到达终点,直接按在监视器下移动即可。
如果可以到达终点,我们由起点出发
每个点在每个方向有三个选择,之后就不会再处理这个格子。
1.直接走
2.按在监视器下走
3.停一秒后直接走。
如果可以直接走,一定不会选择其他的方法,因为同样到达下个位置,其他的方法用时更长。
用时1秒。
不能直接走时,我们可以选择在监视器下走。
用时3秒。
当我们停一秒时,如果可以直接走,那就走。如果不能直接走,那我们就放弃停一秒这个选择。
因为停一秒还在监视下,那只好再停一秒或者按监视下走,这两个选择都不会再最开始就在监视下走更优。
用时2秒。
当我们在这里得到下一个格子的位置和时间的时候,我们还不能马上标记格子访问过。
因为我们有按监视下走的,可能还有某个不按监视下走也到达那个位置的情况。
所以我们只好先把遇到的所有情况扔到优先队列中,在出对时判断就行了。
详见代码
详见我的github ( tiankonguse ) :https://github.com/tiankonguse/ACM/blob/master/hdu/5040.cpp
相关推荐
在C++编程中,反射(Reflection)是一种强大的技术,它允许程序在运行时检查自身的行为和结构。在C++标准库中,反射并不是一个内置特性,但开发者们通过各种方式来实现这一功能,以增强代码的灵活性和可扩展性。...
关于组织参加“第八届‘泰迪杯’数据挖掘挑战赛”的通知-4页
PyMySQL-1.1.0rc1.tar.gz
技术资料分享CC2530中文数据手册完全版非常好的技术资料.zip
docker构建php开发环境
VB程序实例,可供参考学习使用,希望对你有所帮助
pytz库的主要功能 时区转换:pytz库允许用户将时间从一个时区转换到另一个时区,这对于处理跨国业务或需要处理多地时间的数据分析尤为重要。 历史时区数据支持:pytz库不仅提供了当前的时区数据,还包含了历史上不同时期的时区信息,这使得它在处理历史数据时具有无与伦比的优势。 夏令时处理:pytz库能够自动处理夏令时的变化,当获取某个时区的时间时,它会自动考虑是否处于夏令时期间。 与datetime模块集成:pytz库可以与Python标准库中的datetime模块一起使用,以确保在涉及不同时区的场景中时间的准确性。
VB程序实例-为程序添加快捷键.zip
画2、3维的隐含数
pytz库的主要功能 时区转换:pytz库允许用户将时间从一个时区转换到另一个时区,这对于处理跨国业务或需要处理多地时间的数据分析尤为重要。 历史时区数据支持:pytz库不仅提供了当前的时区数据,还包含了历史上不同时期的时区信息,这使得它在处理历史数据时具有无与伦比的优势。 夏令时处理:pytz库能够自动处理夏令时的变化,当获取某个时区的时间时,它会自动考虑是否处于夏令时期间。 与datetime模块集成:pytz库可以与Python标准库中的datetime模块一起使用,以确保在涉及不同时区的场景中时间的准确性。
加载虚拟光驱并打开ma软件.
VB程序实例-图像的缩小.zip
Matlab领域上传的视频均有对应的完整代码,皆可运行,亲测可用,适合小白; 1、代码压缩包内容 主函数:main.m; 调用函数:其他m文件;无需运行 运行结果效果图; 2、代码运行版本 Matlab 2019b;若运行有误,根据提示修改;若不会,私信博主; 3、运行操作步骤 步骤一:将所有文件放到Matlab的当前文件夹中; 步骤二:双击打开main.m文件; 步骤三:点击运行,等程序运行完得到结果; 4、仿真咨询 如需其他服务,可私信博主; 4.1 博客或资源的完整代码提供 4.2 期刊或参考文献复现 4.3 Matlab程序定制 4.4 科研合作
yolo系列算法目标检测数据集,包含标签,可以直接训练模型和验证测试,数据集已经划分好,包含数据集配置文件data.yaml,适用yolov5,yolov8,yolov9,yolov7,yolov10,yolo11算法; 包含两种标签格:yolo格式(txt文件)和voc格式(xml文件),分别保存在两个文件夹中; yolo格式:<class> <x_center> <y_center> <width> <height>, 其中: <class> 是目标的类别索引(从0开始)。 <x_center> 和 <y_center> 是目标框中心点的x和y坐标,这些坐标是相对于图像宽度和高度的比例值,范围在0到1之间。 <width> 和 <height> 是目标框的宽度和高度,也是相对于图像宽度和高度的比例值
推荐几个国外 Java 大佬的优质博客.docx
Arduino一分钟快速在vs code 编译开发Arduino
强网杯objective-c可视化演示5中的常见排序算法,包括选择排序、气泡排序、插入排序、快速排序、堆排序等.zip
VB程序实例,可供参考学习使用,希望对你有所帮助
yolo系列算法目标检测数据集,包含标签,可以直接训练模型和验证测试,数据集已经划分好,包含数据集配置文件data.yaml,适用yolov5,yolov8,yolov9,yolov7,yolov10,yolo11算法; 包含两种标签格:yolo格式(txt文件)和voc格式(xml文件),分别保存在两个文件夹中; yolo格式:<class> <x_center> <y_center> <width> <height>, 其中: <class> 是目标的类别索引(从0开始)。 <x_center> 和 <y_center> 是目标框中心点的x和y坐标,这些坐标是相对于图像宽度和高度的比例值,范围在0到1之间。 <width> 和 <height> 是目标框的宽度和高度,也是相对于图像宽度和高度的比例值
强网杯