Longest Increasing Path in a Matrix

Given a matrix (grid) of non-negative integers, your task is to compute the length of the longest increasing path in the grid. From any cell, you can move in one of the four directions: up, down, left, or right. You may only move to a cell containing a strictly larger value than the current one.

The problem requires you to use an efficient algorithm (e.g., DFS with memoization) to avoid unnecessary recomputation, especially when dealing with larger grids.

Mathematical Formulation:

Let \(G\) be the grid with dimensions \(R \times C\). Define \(f(i,j)\) as the length of the longest increasing path starting from cell \((i,j)\). Then, the recursive relation is given by:

[ f(i,j) = 1 + \max { f(i+1,j), f(i-1,j), f(i,j+1), f(i,j-1) } ]

with the constraint that the next cell must satisfy \(G[i'][j'] > G[i][j]\) and the boundary conditions of the grid.

inputFormat

The first line of input contains two integers, \(R\) and \(C\), representing the number of rows and columns in the grid.

The following \(R\) lines each contain \(C\) space-separated integers representing the grid values.

outputFormat

Output a single integer representing the length of the longest increasing path in the grid.

## sample

3 3
9 9 4
6 6 8
2 1 1

4