题解

题面描述

给定一个由$m*n$ 个单元格组成的矩阵，每个单元格有一个高度值（范围为$1$到$2^{31}-1$）。你可以从任意单元格开始，向上下左右四个方向滑动，每次只能滑向高度严格更低的相邻单元格，且不能重复访问已走过的格子。求满足规则的最长滑行路径长度。

思路

1. 定义状态：

题目内容

某手机应用市场下载量最高的游戏是《欢乐滑雪》游戏。

游戏会自动生成一张 $m*n$ 格子的地形图，每一个单元格，会标明格子的高度，格子的高度可能是从 $1$ 到 $2147483647（即0×7FFFFFFF）$ 中的一个整数。

玩家可以自行选择起点，从玩家指定的任意单元格开始移动，并控制角色往上、下、左、右四个方向滑动。角色无法斜着移动或跑出地图之外，曾经路过的单元格，也不能再重复走。

游戏规则要求，控制角色滑雪的时候，只能从高住低滑，下一步到达的格子的高度，必须小于上一步格子的高度，如果玩家找到在地图满足规则要求的可以滑行的最长路径，就可以过关。请尝试挑战一下吧。

$1<= m,n<= 500$

$1 <= matrix[i] [j]<= 2147483647（即0×7FFFFFFF）$

其中 $i$ 和 $j$ 代表了格子的位置在第 $i$ 行第 $j$ 列，$0<=1<=m-1,0<=j<= n-1$ 。

输入描述

第一行是地图的行数 $m$ 和列数 $n$ ，比如 $4$ $4$ ，值的范围 $[1,500]$ ；

接下来会出现 $m$ 行，每行 $n$ 个数字，每个数字的值的范围 $[1,2147483647]$

输出描述

找到满足条件的最长路径，输出路径的长度。

样例1

输入

3 3
9 8 7
6 6 6
6 6 6

输出

4

说明

在该 $3*3$ 的地图中，满足游戏规则要求的最长滑雪路径是 $9$ $8$ $7$ $6$ ，所以返回路径长度是 $4$ 。请注意，，到达 $6$ 后，不能再往高度为 $6$ 的格子滑。

样例2

输入

1 5
10 11 12 13 14

输出

5

说明

在该 $1*5$ 的地图中，满足游戏规则要求的最长滑雪路径是 $14$ $13$ $12$ $11$ $10$ ，所以返回路径长度是 $5$ 。