Problem5756--攀岩5756: 攀岩
Time Limit: 1.000 Sec Memory Limit: 128 MB
Submit: 47 Solved: 5
[Submit] [Status] [Web Board] [Creator:]Description
艾莉丝站在一座高耸的峭壁前,她计划攀登至峭壁的最高点。峭壁可以被视为一个二维平面,其中艾莉丝的起点坐标为(0,0)。峭壁的高度相当于 yyy 坐标的值,艾莉丝的目标是到达 yyy 坐标为MaxHeight的位置。
峭壁上分布着若干个可供踏足的岩石,这些岩石为艾莉丝提供了攀登的立足点。如果两块岩石在 xxx 方向和 yyy 方向上的距离都不超过 2 个单位(这是一个固定的跳跃范围),那么艾莉丝可以从一块岩石跳到另一块岩石上。
请编写一个程序,判断艾莉丝是否能够成功攀登至峭壁的最高点,并计算出她最少需要踏足多少块岩石(起点岩石不计入统计)。
Input
第一行输入两个整数RockCount和MaxHeight,分别表示峭壁上岩石的数量和峭壁的高度。
接下来RockCount行,每行输入一个岩石的坐标(XPos, yPos),表示岩石在峭壁上的位置。起点坐标(0,0)不会在输入中出现。
Output
如果艾莉丝能够成功攀登至峭壁的最高点,输出她最少需要踏足的岩石数量(不包括起点岩石);如果无法到达,输出-1。
Sample Input
5 3
1 2
6 3
4 1
3 2
7 2
Sample Output
4
HINT
【数据范围】
对于 30%30\%30% 的数据,1≤RockCount≤50,1≤MaxHeight≤101 \le RockCount \le 50,1 \le MaxHeight \le 101≤RockCount≤50,1≤MaxHeight≤10。
对于 100%100\%100% 的数据,1≤RockCount≤50000,1≤yPos<MaxHeight≤200000,xPos≤1061 \le RockCount \le 50000,1 \le yPos < MaxHeight \le 200000 ,xPos \le 10^61≤RockCount≤50000,1≤yPos<MaxHeight≤200000,xPos≤106。
Source/Category
[Submit] [Status]