完成的游戏：场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。
Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy
落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy
跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，
游戏也会结束。设计一个程序，计算Jimmy到地面时可能的最早时间。
输入数据
第一行是测试数据的组数t（0 <= t <= 20）。每组测试数据的第一行是
四个整数N，X，Y，MAX，用空格分隔。N是平台的数目（不包括地面），
X和Y是Jimmy开始下落的位置的横竖坐标，MAX是一次下落的最大高度。接
下来的N行每行描述一个平台，包括三个整数，X1[i]，X2[i]和H[i]。H[i]表示
平台的高度，X1[i]和X2[i]表示平台左右端点的横坐标。1 <= N <= 1000，
-20000 <= X, X1[i], X2[i] <= 20000，0 < H[i] < Y <= 20000（i = 1..N）。
所有坐标的单位都是米。
Jimmy的大小和平台的厚度均忽略不计。如果Jimmy恰好落在某个平台的
边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保Jimmy
一定能安全到达地面。
输出要求：对输入的每组测试数据，输出一个整数，Jimmy到地面时可能的最早时间。
输入样例
1
3 8 17 20
0 10 8
0 10 13
4 14 3
输出样例
23
思路：递归实现
求到达地面的最短时间，将初始位置看作一个平台，地面也看作一个平台，
对各个平台的高度进行排序，用递归来做用最大的一直往下找到地位的最短时间
为了提高效率，利用leftMinList, rightMinList两个列表分别记录平台
左右方向下落的最小时间
python算法实现：
1 # 二维列表的列索引含义：0表示平台左边坐标、1表示平台右边坐标、2表示平台的高度
2 plat_list = []
3 # 递归中为了避免重复计算，提高运算效率，需存储每个i平台左右下落的最小时间
4 # 存储i平台左右下落的最小时间，-1表示没有计算过，
5 leftMinList, rightMinList = [], []
6 # 定义无穷大
7 inf = float('inf')
8 N, MaxHeight = 0, 0
9
10
11 # 计算从平台i到地面的最短时间，往左往右都需要计算才能找到最小值
12 # jimmy从出发下落到第1块板有可能走左边也可能走右边
13 # N表示平台的个数
14 def minDropTime(i, isGoLeft):
15 global plat_list, N, MaxHeight, leftMinList, rightMinList
16 x = 0
17 y = plat_list[i][2] # 当前点的高度
18 # 如果是去左边，就走到左边边上，如果去右边，就走到右边边上
19 if isGoLeft:
20 x = plat_list[i][0]
21 else:
22 x = plat_list[i][1]
23 # 查找如果从左边或者右边下落，是否能到达下一块板
24 # k记录可以下落板的编号
25 k = 0
26 for j in range(i + 1, N + 1):
27 # 如果x落在下一块板的中间，则说明可以从i下落到j板
28 if plat_list[j][0] <= x <= plat_list[j][1]:
29 k = j
30 break
31 # 说明往i下面没有板可以下落
32 if k == 0:
33 if y > MaxHeight:
34 return inf
35 else:
36 return y
37 else: # 有可以下落的板
38 if y - plat_list[k][2] > MaxHeight:
39 return inf
40 else:
41 # =-1，说明该平台下落的最小时间没有计算过
42 if leftMinList[k] == -1:
43 leftMinList[k] = minDropTime(k, True)
44 if rightMinList[k] == -1:
45 rightMinList[k] = minDropTime(k, False)
46 # 如果计算过k平台下落的最小时间，则可以直接计算，不需要重新递归提高效率
47 # 返回平台i往左或者右方向下落的最小值=高度差+min(走k平台左端最小时间,走k平台右端最小时间)
48 return (y - plat_list[k][2]) + min(x - plat_list[k][0] + leftMinList[k],
49 plat_list[k][1] - x + rightMinList[k])
50
51
52 def main():
53 global plat_list, N, MaxHeight, leftMinList, rightMinList
54 # t表示测试数据的组数
55 t = int(input())
56 while t > 0:
57 # N: 平台数目 X, Y: 开始下落位置坐标 MAX: 一次下落最大高度
58 N, X, Y, MaxHeight = 0, 0, 0, 0
59 N, X, Y, MaxHeight = map(int, input().split())
60 # 记录从该平台左边下落的最小时间
61 leftMinList = [-1 for i in range(N + 1)]
62 # 记录从该平台右边下落的最小时间
63 rightMinList = [-1 for i in range(N + 1)]
64 # 平台的二维数组列表
65 plat_list = [[0 for i in range(3)] for i in range(N + 1)]
66
67 # 把jimmy的出发点也当做一个平台，即递归的出发点
68 plat_list[0][0], plat_list[0][1], plat_list[0][2] = X, X, Y
69 for i in range(1, N + 1):
70 plat_list[i] = [int(n) for n in input().split()] # 输入各平台参数
71 # 对平台按高度排序,sorted这个函数要重新覆盖原来的列表内容才会排序
72 plat_list = sorted(plat_list, key=(lambda x: x[2]), reverse=True)
73 # [[8, 8, 17], [0, 10, 13], [0, 10, 8], [4, 14, 3]]
74 min_value = minDropTime(0, True)
75 print("Jimmy到底地面时可能的最早时间为：%d" % min_value)
76 t = t - 1
77
78
79 if __name__ == '__main__':
80 main()