# Increasing Path In Matrix

Posted: 11 Jan, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### Your task is to find and output the longest path length if you start from (0,0) i.e from mat and end at any possible cell (i, j) i.e at mat[i][j].

##### Note :
``````Consider 0 based indexing.
``````
##### Input Format :
``````The first line of input contains an integer ‘T’ denoting the number of test cases. The description of ‘T’ test cases are as follows -:

The first line contains two space-separated positive integers ‘N’, ‘M’ representing the number of rows and columns respectively.

Each of the next ‘N’ lines contains ‘M’ space-separated integers that give the description of the matrix ‘mat’.
``````
##### Output Format :
``````For each test case, print the length of the longest path in the matrix.

Print the output of each test case in a separate line.
``````
##### Note :
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 50
1 <= N <= 100
1 <= M <= 100
-10^9 <= mat[i][j] <= 10^9

Time Limit: 1 sec
`````` Approach 1

Algorithm

• This is a recursive approach.
• Make a recursive function ‘helper(row, col)’ and call this function with (0, 0). In each recursive step do the following-:
• Initialize an integer variable ‘temp’: = 0.
• If cell (row+1, c) exist and mat[row+1][col] > mat[row][col], then recursively call ‘helper(row+1, col)’ and update ‘temp’ with maximum of ‘temp’ and value return by ‘helper(row+1, col)’.
• If cell (row, col+1) exist and mat[row][col+1] > mat[row][col], then recursively call ‘helper(row, col+1)’ and update ‘temp’ with maximum of ‘temp’ and value return by ‘helper(row, col+1)’.
• Return ‘temp’ + 1.
• The value returned by helper(0, 0) will be the length of the longest path start from (0, 0), we need to return this value.