top1编程
← 返回上一页

P4961. 冬季运动

时间限制
1000 ms
内存限制
64 MiB
难度
-
知识点
童程童美
知识点
动态规划基础
知识点
记忆化搜索

题目描述

北京冬奥会让童童爱上了滑雪,滑雪比赛为了获得速度,雪道必须向下倾斜,当童童滑到雪道坡底,不得不再次走上坡或等着缆车,童童想计算出一个区域中最长的滑坡。滑坡的长度由滑过点的个数来计算,区域由一个二维数组给出,数组的每个数字代表点的高度。下面是一个例子: 1668562519681-o8qckn84ofhk3tfmmm.png 童童可以从上图某个点滑向上下左右相邻四个点之一,当且仅当高度减小,在上面的例子中,一条可行的滑坡为 25-24-17-2-1(从 2525 开始到 11 结束),当然 25-24-23-22-21-20-19-18-17-16-15……5-4-3-2-1 更长,长度25,很显然这是最长的一条。

输入格式

输入 nnmm1nm100(1≤n、m≤100)的矩阵 输入 nnmm 个数。

输出格式

输出所有滑坡当中,最长的滑坡长度。

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