Longest Increasing Path in a Matrix

You are given an n×m grid of integers. Your task is to find the length of the longest strictly increasing path in the matrix. From any cell, you can move in four directions: up, down, left, and right. The path must be strictly increasing, meaning each step must move to a cell with a value greater than the current cell.

Note: The path does not need to be contiguous in terms of row or column indices (other than adjacent moves), but every move must be to an adjacent cell.

The problem requires efficient solutions since a brute force method may not pass the time limits for larger grids. Consider using Depth-First Search (DFS) with memoization (dynamic programming) to optimize your solution.

inputFormat

The first line contains two integers n and m, representing the number of rows and columns in the grid, respectively.

This is followed by n lines, each containing m space-separated integers representing the grid.

outputFormat

Output a single integer which is the length of the longest strictly increasing path in the grid.

3 3
9 9 4
6 6 8
2 1 1

4