Longest Increasing Path
Tag(s):

## Algorithms, Dynamic Programming, Medium, Two dimensional

Problem
Editorial
Analytics

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

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.

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...
Your Rating:

## This Problem was Asked in

Challenge Name

DevFactory Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Math > Combinatorics
Уведомления

?