网赛的时候看了这道题,发现就是平常的那种基础搜索题。
由于加了一个特殊条件:可以一次消耗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++ - skyypjack /meta-源码
在线教学质量评价系统可以方便和全面地收集教师教学工作的数据,提供师生网上评教的评分结果,快速集中收集各方面的评教信息,使教务管理部门能够及时了解教学动态和师资情况,为教务老师提供相关决策支持,为职称评聘提供教学工作质量的科学依据,同时减轻了教务老师的工作量。
python-3.10.7-amd64.zip
自研扩散模型高光谱修复网络 基于MST_Plus_Plus 网络改造。 试验数据 扩散模型loss初步测试降到了0.005,比不加扩散loss小了20倍, 训练入口 train_cos_img.py
企业数据治理之数据安全治理方案
这是历年的毕业设计的项目,基于Android的一个红外防盗报警。需要自己添加蜂鸣器和热释电的硬件访问服务。
短视频用户价值研究报告2022
基于springboot的java毕业&课程设计
可运行源码(含数据库脚本)+开发文档+lw(高分毕设项目) java期末大作业毕业设计项目管理系统计算机软件工程大数据专业 内容概要:首先在日常的出行中,老旧城区道路狭窄,容易造成车辆的堵塞,每天早晚,接送孩子的车辆数密集,会造成相应的交通堵塞情况。而同样的,在停车的管理上,一方面我国的停车场面积较少,停车位一位难求,特别是在现在的一些小区里,为了抢停车位而产生的矛盾也日益突出。另一方面在停车场的管理上也存在着较大的管理问题,进车容易出车难是当下的停车场所出现的主要问题。而现在的停车场管理系统眼花缭乱,效果水平也良莠不齐,停车场的管理是当下各大城市的公共设施发展的一大难题,而国家、各大省市也都开 全套项目源码+详尽文档,一站式解决您的学习与项目需求。 适用人群: 计算机、通信、人工智能、自动化等专业的学生、老师及从业者。 使用场景及目标: 无论是毕设、期末大作业还是课程设计,一键下载,轻松部署,助您轻松完成项目。 项目代码经过调试测试,确保直接运行,节省您的时间和精力。 其他说明: 项目整体具有较高的学习借鉴价值,基础能力强的可以在此基础上修改调整,以实现不同的功能。
基于springboot的java毕业&课程设计
微信小程序设计之相关行业源码及图文导入教程
网络游戏开发是一项很大的工程,需要很多综合性的知识。这对于刚刚入门的开发者来说很难理解。本论文从研究开发一个模仿泡泡堂网络游戏的例子出发,讲述网络游戏开发中用到的一些最基本的知识和设计思想,使大家清晰的理解游戏开发的过程。 整个设计中利用java中的swing编程,结合游戏的操作流程,对整个游戏进行精心的设计和大量的测试,实现游戏软件服务器端和客户端的开发,为玩家提供一个友好美观的操作界面,并添加聊天等功能以增加玩家之间的互动性,此外实现了可编辑场景地图的功能,使得游戏内容的更加丰富,玩家交互性更好,确保了游戏更具有趣味性、灵活性,以满足玩家对这款网络游戏的要求。
外东洪路中段.m4a
软考3333333333
附件是Elasticsearch 的全文搜索功能使用方法,文件绿色安全,请大家放心下载,仅供交流学习使用,无任何商业目的!
1.版本:matlab2014/2019a/2021a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
基于springboot的java毕业&课程设计
CCNP TSHOOT 642-832 Official Certification Guide
MySQL8.4.0 LTS(mysql-server_8.4.0-1ubuntu22.04_amd64.deb-bundle.tar)适用于Ubuntu 22.04 Linux (x86, 64-bit)