题目描述： 我们把场地分为一个个的格子，给每个格子标定一个整数，代表这个格子所代表的地面的海拔高度。 比赛的参赛者可以从任意一个格子开始，但只能向相邻的四个格子移动，并且目地格子的高度必须小于现在所在格子的高度。我们假设从一个格子滑行到另一个格子所用的时间为1个单位时间。现在告诉你滑雪场的大小为n*m, 并给你一个n行m列的整数二维列表H，表示每个格子的海拔高度。请你计算出在这个场地上最长能滑行多少时间。 如：
1
2
3
4
5
6
n = 4
m = 4
H= [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10,11,12],
[13,14,15,16]]
则输出 6.
示例： 输入：
1
2
3
4
5
6
7
8
n = 4
m = 4
H = [[1, 12, 11, 10],
[2, 13, 16, 9],
[3, 14, 15, 8],
[4, 5, 6, 7]]
输出：
15
分析:
最直观的一个想法，从最高点向下滑，可能是可以滑的最远的。但是有这样的情况。
[1, 2, 3, 4]
[99, 101, 100, 3]
[100, 102, 88, 104]
从 104 出发，并使不最长的一条路。
所以我们又一个直观的想法，我干脆以每一个位置为起点直接跑一遍，把所有的情况都玩一遍，看看效果。
好的，以上一个想法为起点，我们进行一个测试。
以 104 为起点， 104 => 2， 88 = >1。
以102为起点，102 => 4， 100=>3， 99=>2， 1=>1。
这个时候，我们其实是已经知道了，100的最长距离，99的最长距离的。
并且我们也没有必要从最高点向下滑，还可以从最低点向上走。 这样每一个点可以达到的最高点，就更加的容易确定了。
最后我使用广度优先的方式进行一个遍历。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from queue import Queue
num_lst = []
# 记录已经走到的位置
num_set = set()
# 将所有位置放入到一个列表中，以元组的方式(a, b, c)进行一个保存，其中 a, b 表示位置， c 表示当前位置的海拔高度
for i in range(n):
for j in range(m):
num_lst.append((i,j,H[i][j]))
num_lst.sort(key=lambda x: x[2])
# 用来记录四个防线
pre_lst = [(1, 0), (-1, 0), (0, 1), (0, -1)]
# 记录当前的最大高度
ans = [[0 for i in range(m)] for j in range(n)]
res = 0
while num_lst:
now_item = num_lst.pop()
# print(now_item)
# 当当前位置已经被走到了，我们就不走了。
if (now_item[0], now_item[1]) in num_set:
continue
# 开始准备深度优先
que = Queue()
que.put((now_item[0], now_item[1], 0))
num_set.add((now_item[0], now_item[1]))
while not que.empty():
item = que.get()
x, y, v = item
# 遍历四个方向
for pre in pre_lst:
pre_a, pre_b = pre
tx = x + pre_a
ty = y + pre_b
# 超出边界了就不要再遍历了。
if tx < 0 or tx >= n or ty < 0 or ty >= m:
continue
# print(tx, ty)
# 开始进行判断，首先是是否可以到达，然后判断当前的长度是否可以更长。
if H[tx][ty] < H[x][y] and ans[tx][ty] < v + 1:
# print(tx, ty, v+1)
ans[tx][ty] = v+1
# 记录最长的长度。
res = max(v+1, res)
que.put((tx, ty, ans[tx][ty]))
num_set.add((tx, ty))
print(res)