All Tracks>Algorithms> Dynamic Programming> 2 Dimensional> Problem
Longest Increasing Path
★★★★★

3.7

23 votes
Algorithms, Approved, Dynamic Programming, Medium, Open, Two dimensional
Problem

There is a 2D matrix of N rows and M columns. Rows are number 1 to N from top to bottom and columns 1 to M from left to right. You are standing at (1,1).

From, A [ i ] [ j ] you can move to A [ i + 1 ] [ j ] if A [ i + 1 ] [ j ] > A [ i ] [ j ]. Or, from, A [ i ] [ j ] you can move to A [ i ] [ j + 1 ] if A [ i ] [ j + 1 ] > A [ i ] [ j ].

Moving from (1,1), what is the longest path that you can travel?

Input:
First line contains, T, the number of testcases. Each testcase consists of N, M. Each of the next N lines contain M integers each.

Output:
For each testcase, print the length of the longest path from (1,1).

Constraints:
1 ≤ T ≤ 100
1 ≤ N, M ≤ 100
1 ≤ A[i][j] ≤ 106

Sample Input
3
1 1
1
4 4
1 2 3 4
2 2 3 4
3 2 3 4
4 5 6 7
2 2
1 2
3 4
Sample Output
1
7
3
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In first testcase the path is of 1 length only i.e. (1,1). In second testcase, the path of length 7 is (1,1) , (2,1), (3,1), (4,1), (4,2), (4,3), (4,4). In third case, any of the following paths can be taken. (1,1), (1,2), (2,2) or (1,1), (1,2), (2,2). Both are of length 3.

Contributers:
Editor Image

?