#P1925. Spiderman
Spiderman
题目描述 章鱼博士绑架了蜘蛛侠的女友 MJ,并将她关在西塔。现在,英雄蜘蛛侠必须尽快到达西塔营救她。他需要使用自己的武器 —— 蛛网 —— 完成这一任务。
从蜘蛛侠的公寓(起点)到西塔之间有一条笔直的道路。道路两旁矗立着许多高楼,这些高楼的高度均大于或等于公寓的高度。蜘蛛侠可以向自己与西塔之间的任意建筑物(包括西塔)顶部发射蛛网,然后荡到该建筑物的另一侧。当他完成一次荡摆时,可以再次向另一建筑物发射蛛网,重复这一过程直到到达西塔。图 1 展示了蜘蛛侠从公寓顶部出发到达西塔的过程:他从 A 荡到 B,再从 B 荡到 C,最后从 C 荡到西塔,共使用 次荡摆,这是最优解。
关键规则:
所有建筑物(包括公寓和西塔)均视为直线,且横坐标(Xi)严格递增。
荡摆时,蛛网长度不能超过建筑物高度(即荡摆的水平距离不能超过建筑物高度)。
荡摆方向只能从左到右(不能后退)。
输入
第一行包含测试用例数 。
每个测试用例以整数 开头,表示建筑物数量(包括公寓和西塔)。
接下来 行,每行包含两个整数 ,表示建筑物的横坐标和高度。第一个建筑物是公寓,最后一个是西塔,且所有建筑物按 升序排列, 互不相同。
输出
对每个测试用例,输出到达西塔所需的最少荡摆次数;若无法到达,输出 - 1。
输入输出示例
输入数据 1:
plaintext
2
6
0 3
3 5
4 3
5 5
7 4
10 4
3
0 3
3 4
10 4
输出数据 1:
plaintext
3
2
解释:
第一个测试用例中,蜘蛛侠的荡摆路径为:公寓(0,3)→ (3,5) → (5,5) → 西塔(10,4),共 3 次。 第二个测试用例中,路径为:公寓(0,3)→ (3,4) → 西塔(10,4),共 2 次。