返回小组 开始 2019-10-01 13:00:00

201909月赛(提高组)

结束 2019-10-01 17:00:00
Contest is over.
当前 2024-09-20 05:40:41

B. 【王码编程】九月月赛(提高组)——帮助施工队

描述

在地图学和地理信息学中,高程图是一个十分重要的一中地图表现形式。高程图是指在地图中存储各个位置的高度的矩阵,高程图中某个位置(x, y)的值就代表了该位置的高度信息。例如,如下所示的矩阵就表示了一个中间突出,四周平缓的山丘的高程图。

0 0 0 0 0

0 1 1 1 0

0 1 2 1 0

0 1 1 1 0

0 0 0 0 0

现在,有一支工程队要依据给定的高程图修建公路,要求公路尽可能的平缓。在修建公路之前,需要先找出一条最长的高度递增路径,以减少修建成本。现在这个工程队找到你,希望你帮助他们完成一个简化版的程序:只要求你按照上、下、左、右的方向移动(不需要你按照对角线移动),并且只需要输出这条最长的递增路径的长度即可。例如:

9 9 4

6 6 8

2 1 1

中最长的一条高度递增的路径为1->2->6->9,长度为4。

输入

输入数据为若干行;

第一行为两个整数N, M,代表给出的高程图的行和列,两个数之间使用空格分隔;

接下来的N行,每一行有一个数M,表示一幅高程图,每两个数之间使用空格分隔。

输出

输出数据为一行一个整数,代表你按照上、下、左、右的方向移动(不需要你按照对角线移动),输出的这条最长的递增路径的长度。

样例

输入

3 3
9 9 4
6 6 8
2 1 1

输出

4

提示

对于100%的数据:3\leq N, M\leq 100


Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交