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

时间:2024-01-05 12:30:44

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

由于加了一个特殊条件:可以一次消耗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