推荐订阅源

滑雪:Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。
可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，
你不得不再次走上坡或者等待升降机来载你。
Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字
代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，
一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最
长的一条。输入输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R
行，每行有C个整数，代表高度h，0<=h<=10000。输出输出最长区域的长度。
输入：输入的第一行表示区域的行数R和列数C
(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
输出：输出最长区域的长度。
样例输入
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
样例输出
25
思路：首先要注意的是，该题目所问的是求最长的路径的长度，也由于该测试数据的原因，
很多朋友会想到的一个思路是，从最高点出发，在四个方向中找到最递减最少的方向，以此类推，
一直走到四个方向都不可以走的时候。这个思路的一个缺陷就是有时候，最长的路径并不一定是从最高点开始的，
另外一个误区就是，每次减少高度最少的点也不一定是最长的路径，对于这两点一定要理解。
那么，怎么才能找到最长的路径呢？难道要以每一个地方都为起点来试一遍吗?是的，但是我们要做多一步，
就是每当的走过一个地方，我们得知的它能走的路径长度了，将该长度记录下来，这样当下一次走到该点的时候，
我们就可以直接得到答案而不用再次计算了。
具体方法便是，对每一个点进行遍历，在该点的四个方向中，对于满足不超过边界且比当前高度小的点进行递归，
最后选出递归后返回值最大的值，将其+1便是当前点的路径最大值。
建议参考：https://blog.csdn.net/a769973411/article/details/79414753
python代码实现：

 1 # r表示行数，c表示列数 maxRoute最长距离的值
 2 r, c, maxRoute = 0, 0, 0
 3 areaMatrix, path = [], []
 4 
 5 
 6 def LongestPath(i, j):
 7     global maxRoute,path
 8     leftMaxValue, rightMaxValue, upMaxValue, downMaxValue = 0, 0, 0, 0
 9     # 如果该点的最大路径已经计算过，则直接返回，不需要再递归重复计算，提高效率
10     if path[i][j] > 0:
11         return path[i][j]
12     # 分别与四个方向的点比较，注意行、列不要越界，同时判断如果比当前位置值小，才进行递归
13     # 将当前点的四个方向符合条件的进行递归, 并记录返回的最大值
14     # 这里的符合条件不是四个方向中最小的一个，而是比该点位置低的点都可以
15     # 即对于四个方向的点存在比当前高度低的点都进行递归，选择一个数值最大加上1得到该点的最长路径
16     # 左边
17     if j - 1 >= 0 and areaMatrix[i][j] > areaMatrix[i][j-1]:
18         leftMaxValue = LongestPath(i, j-1)
19     # 右边
20     if j + 1 < r and areaMatrix[i][j] > areaMatrix[i][j+1]:
21         rightMaxValue = LongestPath(i, j+1)
22     # 上边
23     if i - 1 >= 0 and areaMatrix[i][j] > areaMatrix[i-1][j]:
24         upMaxValue = LongestPath(i-1, j)
25     # 下边
26     if i + 1 < c and areaMatrix[i][j] > areaMatrix[i+1][j]:
27         downMaxValue = LongestPath(i+1, j)
28     # 附近4个点的最大值加1，就得到该点的最大距离值
29     path[i][j] = max(leftMaxValue, rightMaxValue, upMaxValue, downMaxValue) + 1
30     if path[i][j] > maxRoute:
31         maxRoute = path[i][j]
32     # print(path)
33     # 返回这个i，j位置的最长路径值
34     return path[i][j]
35 
36 
37 def main():
38     global r, c, areaMatrix, path, maxRoute
39     r, c = map(int, input().split())
40     # 区域二维数组
41     areaMatrix = [[0] for i in range(r)]
42     # print(areaMatrix)
43     for i in range(r):
44         areaMatrix[i] = [int(n) for n in input().split()]  # 输入矩阵
45     # print(areaMatrix)
46     """
47     5 5
48     1 2 3 4 5
49     16 17 18 19 6
50     15 24 25 20 7
51     14 23 22 21 8
52     13 12 11 10 9
53     """
54     # [[1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]]
55     # 假设初始路径的值都是0
56     path = [[0 for i in range(c)] for j in range(r)]  # 作为顶点的最长路径
57     # print(dis)
58 
59     for i in range(r):
60         for j in range(c):
61             LongestPath(i, j)
62     print("滑雪最长距离为：%d" % maxRoute)
63 
64 
65 if __name__ == '__main__':
66     main()