首页 > 试题广场 >

滑雪

[编程题]滑雪
  • 热度指数：4008 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个 的矩阵，矩阵中的数字表示滑雪场各个区域的高度，你可以选择从任意一个区域出发，并滑向任意一个周边的高度严格更低的区域（周边的定义是上下左右相邻的区域）。请问整个滑雪场中最长的滑道有多长？(滑道的定义是从一个点出发的一条高度递减的路线）。
(本题和矩阵最长递增路径类似，该题是当年NOIP的一道经典题)

数据范围： ，矩阵中的数字满足

输入描述:
第一行输入两个正整数 n 和 m 表示矩阵的长宽。
后续 n 行输入中每行有 m 个正整数，表示矩阵的各个元素大小。



输出描述:
输出最长递减路线。

示例1

输入

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

说明

从25出发，每次滑向周边比当前小 1 的区域。 25->24->23->22->......->1
算法知识视频讲解
添加回答
Python3
实习_机器学习_广东或四川_5月中可入职头像 实习_机器学习_广东或四川_5月中可入职
n,m = map(int, input().split())
# print(n,m)
grid = []
for _ in range(n):
    grid.append(list(map(int,input().split())))
# print(grid)
memo = [[0]*m for _ in range(n)]  # 记忆化搜索，当查到这个memo矩阵的时候直接将之前已经计算好的距离拿过来用
directions = [[-1,0],[1,0],[0,-1],[0,1]]
def dfs(x,y):
    if memo[x][y] != 0:  # 当查到这个memo矩阵的时候直接将之前已经计算好的距离拿过来用
        return memo[x][y]
    maxlen = 1
    for direction in directions:
        newx, newy =x+direction[0],y+direction[1]
        if 0<=newx<n and 0<=newy<m and grid[newx][newy]<grid[x][y]:
            maxlen = max(maxlen, dfs(newx,newy)+1)
    return maxlen
res = 0
for i in range(n):
    for j in range(m):
        res = max(res, dfs(i,j))
print(res)
发表于 2025-03-24 15:03:43 回复(0)
提交观点

问题信息

动态规划 记忆化搜索 图 拓扑排序 递归
难度：
1条回答 5956浏览

热门推荐

通过挑战的用户

查看代码

相关试题

滑雪

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号