2 shunfurh shunfurh 于 2017.08.27 17:05 提问

Haunted Graveyard

Tonight is Halloween and Scared John and his friends have decided to do something fun to celebrate the occasion: crossing the graveyard. Although Scared John does not find this fun at all, he finally agreed to join them in their adventure. Once at the entrance, the friends have begun to cross the graveyard one by one, and now it is the time for Scared John. He still remembers the tales his grandmother told him when he was a child. She told him that, on Halloween night, "haunted holes" appear in the graveyard. These are not usual holes, but they transport people who fall inside to some point in the graveyard, possibly far away. But the scariest feature of these holes is that they allow one to travel in time as well as in space; i.e., if you fall inside a "haunted hole", you appear somewhere in the graveyard a certain time before (or after) you entered the hole, in a parallel universe otherwise identical to ours.

The graveyard is organized as a grid of W × H cells, with the entrance in the cell at position (0, 0) and the exit at (W − 1, H − 1). Despite the darkness, Scared John can always recognize the exit, and he will leave as soon as he reaches it, determined never to set foot anywhere in the graveyard again. On his way to the exit, he can walk from one cell to an adjacent one, and he can only head to the North, East, South or West. In each cell there can be either one gravestone, one "haunted hole", or grass:

If the cell contains a gravestone, you cannot walk over it, because gravestones are too high to climb.
If the cell contains a "haunted hole" and you walk over it, you will appear somewhere in the graveyard at a possibly different moment in time. The time difference depends on the particular "haunted hole" you fell into, and can be positive, negative or zero.
Otherwise, the cell has only grass, and you can walk freely over it.
He is terrified, so he wants to cross the graveyard as quickly as possible. And that is the reason why he has phoned you, a renowned programmer. He wants you to write a program that, given the description of the graveyard, computes the minimum time needed to go from the entrance to the exit. Scared John accepts using "haunted holes" if they permit him to cross the graveyard quicker, but he is frightened to death of the possibility of getting lost and being able to travel back in time indefinitely using the holes, so your program must report these situations.

Figure: Sample graveyard
Figure: Sample graveyard
The above figure illustrates a possible graveyard (the second test case from the sample input). In this case there are two gravestones in cells (2, 1) and (3, 1), and a "haunted hole" from cell (3, 0) to cell (2, 2) with a difference in time of 0 seconds. The minimum time to cross the graveyard is 4 seconds, corresponding to the path:

If you do not use the "haunted hole", you need at least 5 seconds.


The input consists of several test cases. Each test case begins with a line containing two integers W and H(1 ≤ W, H ≤ 30). These integers represent the width W and height H of the graveyard. The next line contains an integer G(G ≥ 0), the number of gravestones in the graveyard, and is followed by G lines containing the positions of the gravestones. Each position is given by two integers X and Y(0 ≤ X < W and 0 ≤ Y < H).

The next line contains an integer E(E ≥ 0), the number of "haunted holes", and is followed by E lines. Each of these contains five integers X1, Y1, X2, Y2, T. (X1, Y1) is the position of the "haunted hole" (0 ≤ X1 < W and 0 ≤ Y1 < H). (X2, Y2) is the destination of the "haunted hole" (0 ≤ X2 < W and 0 ≤ Y2 < H). Note that the origin and the destination of a "haunted hole" can be identical. T(−10000 ≤ T ≤ 10000) is the difference in seconds between the moment somebody enters the "haunted hole" and the moment he appears in the destination position; a positive number indicates that he reaches the destination after entering the hole. You can safely assume that there are no two "haunted holes" with the same origin, and the destination cell of a "haunted hole" does not contain a gravestone. Furthermore, there are neither gravestones nor "haunted holes" at positions (0,0) and (W-1,H-1).

The input will finish with a line containing 0 0, which should not be processed.


For each test case, if it is possible for Scared John to travel back in time indefinitely, output Never. Otherwise, print the minimum time in seconds that it takes him to cross the graveyard from the entrance to the exit if it is reachable, and Impossible if not.

Sample Input

3 3
2 1
1 2
4 3
2 1
3 1
3 0 2 2 0
4 2
2 0 1 0 -3
0 0
Sample Output



devmiao   Ds   Rxr 2017.08.27 23:52
Csdn user default icon
Haunted Graveyard
Haunted Graveyard Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 251   Accepted: 61 Description Tonight is Halloween and Scared John and his friends  have dec
poj 3878 zoj 3391 haunted graveyard
最短路 SPFA,题目没说清楚如果到达洞的出口又是洞的出口怎么解决,也没清楚 time indefinitely 是什么意思,而且如果洞的出口和洞的入口在同一个格子,如果时间是负的可以算 Never,可是如果是正的又该怎么算?,这样永远走不出去也走不回去,这又算 Never 还是
hdu 4076 Haunted Graveyard - spfa(负权回路)
/* hdu 4076 Haunted Graveyard - spfa(负权回路) 题意:有n*m个点,每一点可以向四个方向走,有些点是墓地不能走,有些点是山洞,当你走到该点时会传送到另外一点,所花费的时间有可能是个正数也可能是个负数 也可能是0。起点是(0,0),目的地是(n-1,m-1),题目保证起点和终点不会是墓地也不会是山洞。如果有可能永远都到达不了终点也就是该图存在负权回路,输出Nev
题意: 在一个周长为10000的圆上有平均分布着n个雕像,现在在这个圆上加上m个雕像,问想要平均分布(n+m)个雕像,最少要把原来的n个雕像一共移动多少距离。 思路: 先求出n个雕像和(n+m)在圆上的平均距离。把n个雕像的圆以任意一个点为起点,求出第i个点的值,用第i个点的值除以(n+m)的圆的点的平均值(化为整数)。求得(n+m)上离i最近的一个点,用这点的值乘以(n+m)的点的平均值。
The Graveyard Book
书名:The Graveyard Book 作者:Gaiman, Nei 篇幅: 140P 蓝思值:820L 用时: 7天【透析成果】 这是我读完的第9本英文原著,一共用词典查了62个单词。 下面是所有单词: 1, homecoming [‘homkʌmɪŋ] n. 归国;同学会;省亲回家 2, toddler [‘tɑdlɚ] n. 学步的小孩;幼童装 3, crib
Haunted Maze 3D - The sequel to haunted maze comes with isom
Haunted Maze 3D - The sequel to haunted maze comes with isometric graphics and improved AI since the ghost use their line of site to find you!
Uva 1388 Graveyard - 水题
题目描述:lrj厚白书第一章第四到例题 题目分析:如果插入点的个数是n的倍数,那么不需要移动这n个点。如果想要移动的距离最短,那么不难想象最多只需要要移动(n-1)个点。所以可以在这n个点中选取一个参照点,其它点的位置是相对于该参照点的。所以在没有加入m个点之前,这n个点都有一个相对与参照点的以为坐标pi,那么在插入m个点之后,这n个点会有确定的位置。然后在判断pi与这写位子的最短距离即可。
#include #include #include using namespace std; int main(int argc, char const *argv[]) { int n,m; while(scanf("%d%d",&n,&m)==2) { double ans=0; for (int i = 1; i { double pos=(double)i
Uva Oj 1388 - Graveyard
依旧是训练指南上的例题,不过这个事我自己写的 和lrj中的没有关系 1Y 建了个结构体来标记这个点是原来的点还是新的点 然后排序 接下来找到序列中的新出现的点 如果这个点左边(右边)是原本点,则记录距离,并更新到z中 如果两边都不是原本点,那么原本点一定不会舍近求远,无视掉就好了 接下来去z的前n项求和,表示n个原本点的最优选择分别是某n个新点 然后转化输出就好了 #inclu