Home => ProblemSet => [DAG模型]矩阵中的最长递增路径
Problem2283--[DAG模型]矩阵中的最长递增路径

2283: [DAG模型]矩阵中的最长递增路径

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 0
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

给定一个 n * m 整数矩阵 matrix ,找出其中 长递增路径 的长度。
对于每个单元格,你可以往上,下,左,右四个方向移动。 你 不能对角线 方向上移动或移动到 边界外(即不允许环绕)。

Input

第一行n, m,表示矩阵的行数和列数;
接下来一个n行m列的矩阵;

Output

一个正整数,表示最长递增路径的长度

Sample Input Copy

3 3
9 9 4
6 6 8
2 1 1

Sample Output Copy

4

HINT

1 <= m, n <= 200
0 <= 矩阵元素值 <= 2^31 -1


样例解释:
样例一答案:1 2 6 9


样例二:
输入:
3 3
3 4 5
3 2 6
2 2 1
输出:
4
样例二答案:3 4 5 6

Source/Category