`
tiankonguse
  • 浏览: 16125 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

2014年北京网络赛 Instrusive HDU 5040 题解 优先队列

阅读更多

网赛的时候看了这道题,发现就是平常的那种基础搜索题。

 

由于加了一个特殊条件:可以一次消耗3秒或原地停留1秒。

 

那就不能使用简单的队列了,需要使用优先队列才行。

 

题意

 

告诉一副地图:一个起点,一个终点,若干墙,若干监视器,剩下的是空地。

 

起点,终点,监视器都算空地。

监视器初始值会指定一个方向,共有四个方向。

监视器每秒顺时针转动到下个方向。

监视器视野距离为2.

在监视器的位置或在监视器面向的格子是监视区域。

 

普通的移动一格需要消耗1秒时间。

在监视器下移动一格需要消耗3秒时间。

如果呆在原地不动,即使在监视器视野内也不会被发现。

 

求最少时间从起点到达终点。

不能到达输出-1。


思路

 

第一步显然是先算算是不是可以到达终点,直接按在监视器下移动即可。

如果可以到达终点,我们由起点出发

每个点在每个方向有三个选择,之后就不会再处理这个格子。

1.直接走

2.按在监视器下走

3.停一秒后直接走。

 

如果可以直接走,一定不会选择其他的方法,因为同样到达下个位置,其他的方法用时更长。

用时1秒。

 

不能直接走时,我们可以选择在监视器下走。

用时3秒。

当我们停一秒时,如果可以直接走,那就走。如果不能直接走,那我们就放弃停一秒这个选择。

因为停一秒还在监视下,那只好再停一秒或者按监视下走,这两个选择都不会再最开始就在监视下走更优。 

用时2秒。


当我们在这里得到下一个格子的位置和时间的时候,我们还不能马上标记格子访问过。

因为我们有按监视下走的,可能还有某个不按监视下走也到达那个位置的情况。



所以我们只好先把遇到的所有情况扔到优先队列中,在出对时判断就行了。


详见代码

 

详见我的github ( tiankonguse ) :https://github.com/tiankonguse/ACM/blob/master/hdu/5040.cpp

 

这篇博客与 tiankonguse 的个人网站保持同步 http://tiankonguse.com/record/record.php?id=707
 
0
0
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics