2 shunfurh shunfurh 于 2017.01.03 01:58 提问

Here We Go(relians) Again

Description

The Gorelians are a warlike race that travel the universe conquering new worlds as a form of recreation. Given their violent, fun-loving nature, keeping their leaders alive is of serious concern. Part of the Gorelian security plan involves changing the traffic patterns of their cities on a daily basis, and routing all Gorelian Government Officials to the Government Building by the fastest possible route.

Fortunately for the Gorelian Minister of Traffic (that would be you), all Gorelian cities are laid out as a rectangular grid of blocks, where each block is a square measuring 2520 rels per side (a rel is the Gorelian Official Unit of Distance). The speed limit between two adjacent intersections is always constant, and may range from 1 to 9 rels per blip (a blip, of course, being the Gorelian Official Unit of Time). Since Gorelians have outlawed decimal numbers as unholy (hey, if you're the dominant force in the known universe, you can outlaw whatever you want), speed limits are always integer values. This explains why Gorelian blocks are precisely 2520 rels in length: 2520 is the least common multiple of the integers 1 through 9. Thus, the time required to travel between two adjacent intersections is always an integer number of blips.

In all Gorelian cities, Government Housing is always at the northwest corner of the city, while the Government Building is always at the southeast corner. Streets between intersections might be one-way or two-way, or possibly even closed for repair (all this tinkering with traffic patterns causes a lot of accidents). Your job, given the details of speed limits, street directions, and street closures for a Gorelian city, is to determine the fastest route from Government Housing to the Government Building. (It is possible, due to street directions and closures, that no route exists, in which case a Gorelian Official Temporary Holiday is declared, and the Gorelian Officials take the day off.)

Gorelian city
The picture above shows a Gorelian City marked with speed limits, one way streets, and one closed street. It is assumed that streets are always traveled at the exact posted speed limit, and that turning a corner takes zero time. Under these conditions, you should be able to determine that the fastest route from Government Housing to the Government Building in this city is 1715 blips. And if the next day, the only change is that the closed road is opened to two way traffic at 9 rels per blip, the fastest route becomes 1295 blips. On the other hand, suppose the three one-way streets are switched from southbound to northbound (with the closed road remaining closed). In that case, no route would be possible and the day would be declared a holiday.

Input

The input consists of a set of cities for which you must find a fastest route if one exists. The first line of an input case contains two integers, which are the vertical and horizontal number of city blocks, respectively. The smallest city is a single block, or 1 by 1, and the largest city is 20 by 20 blocks. The remainder of the input specifies speed limits and traffic directions for streets between intersections, one row of street segments at a time. The first line of the input (after the dimensions line) contains the data for the northernmost east-west street segments. The next line contains the data for the northernmost row of north-south street segments. Then the next row of east-west streets, then north-south streets, and so on, until the southernmost row of east-west streets. Speed limits and directions of travel are specified in order from west to east, and each consists of an integer from 0 to 9 indicating speed limit, and a symbol indicating which direction traffic may flow. A zero speed limit means the road is closed. All digits and symbols are delimited by a single space. For east-west streets, the symbol will be an asterisk '*' which indicates travel is allowed in both directions, a less-than symbol '<' which indicates travel is allowed only in an east-to-west direction, or a greater-than symbol '>' which indicates travel is allowed only in a west-to-east direction. For north-south streets, an asterisk again indicates travel is allowed in either direction, a lowercase "vee" character 'v' indicates travel is allowed only in a north-to-south directions, and a caret symbol '^' indicates travel is allowed only in a south-to-north direction. A zero speed, indicating a closed road, is always followed by an asterisk. Input cities continue in this manner until a value of zero is specified for both the vertical and horizontal dimensions.

Output

For each input scenario, output a line specifying the integer number of blips of the shortest route, a space, and then the word "blips". For scenarios which have no route, output a line with the word "Holiday".

Sample Input

2 2
9 * 9 *
6 v 0 * 8 v
3 * 7 *
3 * 6 v 3 *
4 * 8 *
2 2
9 * 9 *
6 v 9 * 8 v
3 * 7 *
3 * 6 v 3 *
4 * 8 *
2 2
9 * 9 *
6 ^ 0 * 8 ^
3 * 7 *
3 * 6 ^ 3 *
4 * 8 *
0 0
Sample Output

1715 blips
1295 blips
Holiday

1个回答

caozhy
caozhy   Ds   Rxr 2017.01.09 23:50
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
HDU 2722 Here We Go(relians) Again 最短路
Here We Go(relians) Again Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 171 Accepted Submission(s): 109   Problem Descri
Here We Go(relians) Again
Here We Go(relians) Again Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 169    Accepted Submission(s): 107  
shell-002 while
0 #!/bin/bash i=1 while ((i<20)) do ((i=i+1)) done echo $i 1. baby_rocker.sh baby_rocker.sh #!/bin/bash while [ 1=1 ] do eject eject -t done 2. repeat.sh #!/bin/bash de
POJ 3653 Here We Go (relians) Again
万恶的输入
HDU 2722 Here We Go(relians) Again
<br />就是题目长...  只要构好图就可以了。<br />1:each block is a square measuring 2520 rels per side 。<br />2:The speed limit between two adjacent intersections is always constant, and may range from 1 to 9 rels per blip<br />每条边的边长都是2520,速度1-9. 所以按time = 2520 / speed 构图
Here We Go(relians) Again hdu 2722
/* 题目其实很简单,只是题目太长了,看懂有点不容易,最郁闷的是以开始就看懂了的, 只是2520/8 = 290 了,结果导致自己看懂的想法彻底崩溃,于是就在纠结中挣扎,痛苦ing。。 没想到这么弱智的毛病也犯 题目大致意思从起点到终点找一条花费时间最少的路,并输出(blips其实就是时间) 每条路的距离是2520 (是1 到 9的最小公倍数 可以不管的), 给你两点之间最大速度 P 两点的时间 t = 2520 / p;注意 p = 0的是,两点为断路,接下来就是构图共有 v =
hdu 2722 Here We Go(relians) Again
点击打开链接 /* Review : 这题其实没什么难度,就是题目特别恶心,又臭又长,再加上制图也很恶心, 第一次做这么恶心的题,于是乎拖了几个小时。 把输入分为横向路 和 纵向路 来处理会比较方便一点,这个想了好久啊……好笨好笨 */--------------------------------------------------------------------------
hdu2722——Here We Go(relians) Again
Here We Go(relians) Again Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 711    Accepted Submission(s): 347 Problem Description The Go
HDU 2722:Here We Go(relians) Again
题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=2722 题目翻译: 不得不吐槽,这题题目太长了,还是英文,看的吐了,不过最终还是看明白了。 给出N,M;   则就有(N+1)行,(M+1)列 然后分别给出的是 第一行中相邻列的关系 第二行与第一行同列点的关系 第二行中相邻列的关系 第三行与第二行同列点的关系 第三
HDU-2722-Here We Go(relians) Again
ACM模版描述 题解题目好难读懂啊,于是看了大牛(shuangde800)的题解,发现好水啊,基础的最短路,就是处理输入比较麻烦,读入数据时比较花,看不懂题真心搞不好这道题~~~代码#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <utility>using namespace s