3 solutions
-
0
题面描述
塔子哥是一位极限滑雪爱好者,他希望探索滑雪场的最长路径。给定一个滑雪场的高度矩阵,要求滑雪路径从一个点滑向周围的相邻点,且下一个点的高度必须严格低于当前点。输入包括矩阵的行数和列数,以及每个点的高度。输出最长的滑雪路径长度。你是否想要了解具体的解题思路或方法?
题解:记忆化搜索
定义表示以点开始的最大路径,由于只能向比它权值低的点走,因此对于所有可以前往的路径
应该有
初始化所有的,然后对于每一个点,跑一遍DFS,加一个记忆化搜索的判断
方法步骤
-
定义数据结构:
- 使用二维数组
g
存储滑雪场的高度。 - 使用二维数组
f
存储从每个点出发的最大路径长度,初始值设为-1
表示尚未计算。
- 使用二维数组
-
DFS 函数:
- 通过递归的方式计算以
(x, y)
为起点的最大路径长度。如果已经计算过(f[x][y] != -1
),直接返回已存储的结果。 - 否则,将路径长度初始化为 1(包括当前点)。
- 检查四个方向(上、下、左、右),如果相邻点高度低于当前点,递归调用 DFS 计算相邻点的最大路径长度,并更新当前点的最大路径长度。
- 通过递归的方式计算以
-
主函数:
- 输入滑雪场的高度信息。
- 对于每个点调用 DFS 函数,计算并更新最大路径长度。
-
输出结果:
- 最后,输出所有点中找到的最长路径长度。
C++
Java
Python3
-
- 1
Information
- ID
- 67
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 6
- Tags
- # Submissions
- 136
- Accepted
- 42
- Uploaded By