某手机应用市场下载量最高的游戏是《欢乐滑雪》游戏。
游戏会自动生成一张 m∗n 格子的地形图,每一个单元格,会标明格子的高度,格子的高度可能是从 1 到 2147483647(即0×7FFFFFFF) 中的一个整数。
玩家可以自行选择起点,从玩家指定的任意单元格开始移动,并控制角色往上、下、左、右四个方向滑动。角色无法斜着移动或跑出地图之外,曾经路过的单元格,也不能再重复走。
游戏规则要求,控制角色滑雪的时候,只能从高住低滑,下一步到达的格子的高度,必须小于上一步格子的高度,如果玩家找到在地图满足规则要求的可以滑行的最长路径,就可以过关。请尝试挑战一下吧。
给定一个由m∗n 个单元格组成的矩阵,每个单元格有一个高度值(范围为1到231−1)。你可以从任意单元格开始,向上下左右四个方向滑动,每次只能滑向高度严格更低的相邻单元格,且不能重复访问已走过的格子。求满足规则的最长滑行路径长度。