2 shunfurh shunfurh 于 2017.09.04 23:11 提问

Catch The Heart

Problem Description
Do you know Popeye? He likes spinach(菠菜) very much. Maybe you have played some games about him. Now here comes one game.

There are many boards, on one board there is a heart, Popeye wants to catch the heart and send it to his GF, Oliver, so that, she will be happy.

At the beginning, Popeye is on one board, and the heart is on another board. Every board is described as h, l, and r, the height, the left end and the right end. You can look it as a line (l, h) (r, h) in XY coordinate system. Popeye can walk on the board, jump from one board to another.

Notes:
1.He can walk on a board 1 unit per second.
2.He can only jump vertically(垂直地), and it takes 1s for each jumping.
3.He can jump only 1 unit high, so that he can jump only if the difference of the boards’ height is 1.
4.He can only jump up to the left or right point of the board.
5.He can only jump down from the left or right point of the board.

You can look the picture:

The problem is, find the shortest time to catch the heart.

Input
The first line of the input contains an integer T (T <= 20) which means the number of test cases. For each case, first line is an integer m (2 <= m <= 10000) which means the number of the boards. Then comes two lines, the first line contains h0, l0, r0, p0 (l0 <= p0 <= r0), which mean the information of the board and the position that the heart on it. Next line contains h1, l1, r1, p1 (l1 <= p1 <= r1), which mean the information of the board and the position that Popeye on it. Then comes m-2 lines, each contains hi, li, ri mean the ith (2 <= i < m) board’s information.

There is no common point or common parts for every two boards.
All inputs are integers, for each board, 0 <= h <= 10000, 0 <= l < r <= 100000000.

Output
For each case, output the shortest time to catch the heart if Popeye can catch it, otherwise output -1.

Sample Input
3
3
3 4 5 5
1 0 10 0
4 1 2
2
1 1 99999999 1
0 0 100000000 100000000
5
4 0 5 0
0 0 5 0
1 5 10
2 6 15
3 5 10

Sample Output
-1
100000000
24

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.19 05:26
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
cloudera manager5.7.0中编译oozie的hive workflow一直heart beat 问题总结
这个问题折腾了很久,现在还是有点困惑,废话少说,先把我趟的KENG说一下: 1、修改/tmp 文件的权限    ------->  sudo chmod a+wrx /tmp 2、把mysql 的驱动jar包放到 hdfs上 3、把hive-site.xml(一般在/opt/cm-5.7.0/run/cloudera-scm-agent/process/64-hue-HUE_SERVER/h
09.My Heart Will Go On[我心永恒]_萨克斯_[APE][1/2]
(这是第一部分,还有一部分要下载) 09.My Heart Will Go On[我心永恒]_萨克斯_[APE] 萨克斯版的APE文件,可以用 千千静听 转换为MP3格式,由于文件较大分为两个文件 09.My Heart Will Go On[我心永恒]_萨克斯_[APE].part1 09.My Heart Will Go On[我心永恒]_萨克斯_[APE].part2 两个都在我的资源里面,下载后放到同一文件夹下进行解压即可! 专辑:The Essential Kenny G 肯尼·基精萃 CD2 艺术家:Kenny G 肯尼·基
无意间看到这样一首歌 Take me to your heart
    和未婚妻正式分手好些时候了,虽然她现在还和我住在同一屋檐下,但心却不在了。周未的晚上,她出去陪新男友了,一个人无聊的上网翻看别人的BLOG,无意间看到这样一首歌 Take me to your heart,张学友《吻别》的英文翻版(呵呵,我一直以为是原版,经网友指正才知,谢过了),我一向比较爱听英文版的。于是当然上网搜一把,原来很多有都很喜爱这首歌,还有一对恋人,还把它翻译成了中文。把我带
I Heart Logs.pdf
I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf I Heart Logs.pdf
宫崎步 brave heart 歌词加谐音
Brave Heart歌:宫崎步作词:大森祥子作曲:太田美知彦编曲:太田美知彦逃げたりあきらめるコトは 谁も不论是谁 都有想去逃避的时候一瞬あればできるから 歩き続けよう只要在那一刻发挥出潜藏的那种力量 便可以清除前路上的障碍君にしかできないコトがある 青い星に一定有些什么事情是你才做到的 使这个蓝色星球光がなくせぬように可以继续闪耀着光芒つかめ! 描いた梦を抓紧着 你所拥有的梦想まもれ! 大事な
Follow my heart!追随我心(选择自己喜欢的工作)
上次bert君讲述了自己选择offer的纠结,小伙伴们可以回复关键字“3022”即可查看文章《传统互联网or新兴互联网,向左or向右?》,今天来讲讲bert君后续的经历。上篇文章讲到传统互联网和新兴互联网,现在bert君觉得这是个伪命题。大多数的人认为:传统互联网的对立面是移动互联网。 其实互联网本身是没有区别的,网只有一个,不分互联网和移动互联网,从这个角度,这个问题关键在于终端。移动终端的出现
take me to your heart 我太喜欢这首歌了.听过张学友的吻别了吗?你,如果你没听过,那你应该听听这首,如果你听过了,那你更应该听听这首歌!
take me to your heart 歌词  Hiding from the rain and snow Trying to forget but I wont let go Looking at a crowded street Listening to my own heart beat So many people all around the world T
【分享】To Heart回忆永恒1+2系列【日文+汉化硬盘版】[带全CG存档&攻略+各类补丁]
To Heart Leaf Visual Novel Series Vol.3 发售日期:1999-07-08 发售公司:Leaf 游戏平台: PC 语言:日文 ▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ ToHeart PSE: i-7 ▬▬▬▬▬▬▬▬▬▬
Most of the shadows of life are caused by standing in our own sunshine.
Most of the shadows of life are caused by standing in our own sunshine.
UCI 心脏病数据集heart-disease
The file cleveland.data has been unfortunately messed up when we lost node cip2 and loaded the file on node ics. The file processed.cleveland.data seems to be in good shape and is useable (for the 14 attributes situation). I'll clean up cleveland.data as soon as possible. Bad news: my original copy of the database appears to be corrupted. I'll have to go back to the donor to get a new copy. David Aha