网赛的时候看了这道题,发现就是平常的那种基础搜索题。
由于加了一个特殊条件:可以一次消耗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++标准库中,反射并不是一个内置特性,但开发者们通过各种方式来实现这一功能,以增强代码的灵活性和可扩展性。...
基于springboot大学生就业信息管理系统源码数据库文档.zip
基于java的驾校收支管理可视化平台的开题报告
时间序列 原木 间隔5秒钟 20241120
毕业设计&课设_基于 Vue 的电影在线预订与管理系统:后台 Java(SSM)代码,为毕业设计项目.zip
基于springboot课件通中小学教学课件共享平台源码数据库文档.zip
基于java的网上购物商城的开题报告
Delphi人脸检测与识别Demo1fdef-main.zip
基于java的咖啡在线销售系统的开题报告
基于java的自助医疗服务系统的开题报告.docx
内容概要:本文档全面介绍了Visual Basic(VB)编程语言的基础知识和高级应用。首先概述了VB的基本特性和开发环境,随后详细讲述了VB的数据类型、变量、运算符、控制结构、数组、过程与函数、变量作用域等内容。接着介绍了窗体设计、控件使用、菜单与工具栏的设计,文件操作、数据库访问等关键知识点。最后讨论了VB的学习方法、发展历史及其在桌面应用、Web应用、数据库应用、游戏开发和自动化脚本编写等领域的广泛应用前景。 适合人群:初学者和中级程序员,尤其是希望快速掌握Windows桌面应用开发的人群。 使用场景及目标:①掌握VB的基础语法和开发环境;②学会使用VB创建复杂的用户界面和功能完整的应用程序;③理解数据库操作、文件管理和网络编程等高级主题。 其他说明:Visual Basic是一种简单易学且功能强大的编程语言,尤其适合用于开发Windows桌面应用。文中不仅覆盖了基础知识,还包括了大量的实用案例和技术细节,帮助读者快速提升编程技能。
基于java的疫情期间高校防控系统开题报告.docx
基于springboot+vue社区老年人帮扶系统源码数据库文档.zip
基于java的超市商品管理系统的开题报告.docx
基于SpringBoot房屋买卖平台源码数据库文档.zip
xdu限通院23微处理器系统与应用大作业(两只老虎),适应于汇编语言keil软件,
<项目介绍> - 新闻类网站系统,基于SSM(Spring、Spring MVC、MyBatis)+MySQL开发,高分成品毕业设计,附带往届论文 - 不懂运行,下载完可以私聊问,可远程教学 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.md文件(如有),仅供学习参考, 切勿用于商业用途。 --------
基于java的学生网上请假系统的开题报告.docx
社会经济繁荣发展的今天,电子商务得到了飞速发展,网上交易越来越彰显出其独特的优越性,在人们的日常生活中,出现了各种类型的交易网站。其中一个就是车辆易主交易网站,它是一个服务于用户买卖二手车辆的交易网站,为用户提供了平等互利、方便快捷的网上交易平台,通过这一类型的网站,用户可自由出售和购买车辆。 本课题主要根据车辆本身的特性,充分发挥互联网的特点与优势,构建一个以二手车辆为商品、基于互联网平台的车辆易主业务交易管理系统,并根据车辆易主业务交易管理系统的应用需求,进行需求分析,进而对网站系统作规划设计。采用IDEA为运行平台,以SSH为框架,运用HTML语言、JSP技术、MySql数据库、JSP与后台数据库链接等关键技术建设二手车网上交易系统,构建车辆易主交易系统的会员注册与登录,网站首页展示、用户发布商品车辆,用户求购商品车辆,分页浏览、购物系统、用户后台管理、管理员用户后台管理等功能,并使这些功能得以实现并更好为用户服务。网站整体构建完成且测试成功后,用户可以进入网站进行注册、登录,登录后,用户可以在网站上发布自己的闲置车辆或者寻找想要购买的车辆,还可以收藏车辆,管理发布和收藏的车辆,
SQLite3的向量扩展库,windows dll,版本0.1.5