Longest Increasing Path in a Matrix

Given a matrix of integers, your task is to find the length of the longest increasing path in the grid. From any cell, you can move in four directions: up, down, left, or right. You can only move to a cell with a strictly higher value than the current cell.

Note: The movement direction is restricted to the four cardinal directions only. Paths that revisit the same cell or include cells with equal or decreasing values are not valid.

Calculate the length of the longest increasing path, and output that length. Use the provided input format and produce output through standard output.

The problem can be formally described as follows:

Let \( grid \) be an \( m \times n \) matrix where \( grid[i][j] \) represents the integer at row \( i \) and column \( j \). The goal is to find a path \( p = \{(i_1,j_1), (i_2,j_2), \dots, (i_k,j_k)\} \) such that for all \( 1 \leq t grid[i_t][j_t] \quad \text{and} \quad (i_{t+1},j_{t+1}) \text{ is adjacent to } (i_t,j_t). \] The objective is to maximize \( k \), the length of this path.

inputFormat

The first line of input contains two space-separated integers \( m \) and \( n \) indicating the number of rows and columns in the matrix.

The next \( m \) lines each contain \( n \) space-separated integers representing the grid.

outputFormat

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

3 3
9 9 4
6 6 8
2 1 1

4