Longest Increasing Path in a Matrix

You are given an n x m integer matrix. Your task is to find the length of the longest strictly increasing path in the matrix. From each cell, you can move to any of its four adjacent cells (up, down, left, right) if the value of the adjacent cell is strictly greater than the value of the current cell.

Formally, let the matrix be denoted as \( A \) where \( A_{i,j} \) represents the element in the \( i \)th row and \( j \)th column. A valid path \( (i_1, j_1), (i_2, j_2), \dots, (i_k, j_k) \) must satisfy:

[ A_{i_1,j_1} < A_{i_2,j_2} < \cdots < A_{i_k,j_k} ]

Your goal is to compute the maximum \( k \) over all such paths in the matrix.

inputFormat

The input is provided via stdin and has the following format:

1. The first line contains two integers, \( n \) and \( m \), representing the number of rows and columns respectively.
2. The next \( n \) lines each contain \( m \) integers separated by spaces, representing the rows of the matrix.

outputFormat

Output a single integer which is the length of the longest strictly increasing path in the matrix. The output should be printed to stdout.

3 3
9 9 4
6 6 8
2 1 1

4