Longest Increasing Path in a Matrix

You are given a matrix of integers with m rows and n columns. Your task is to determine the length of the longest increasing path in the matrix. In this problem, you can move from a cell to one of its four adjacent neighbors (up, down, left, right), and you may only move to a neighbor if its value is strictly greater than the current cell's value.

Formally, let the matrix be represented as \( A \) with dimensions \( m \times n \). You need to find the maximum length \( L \) of a path \( (i_1, j_1), (i_2, j_2), \dots, (i_L, j_L) \) such that for each \( k \) from \( 1 \) to \( L-1 \), the following conditions hold:

• \( A[i_{k+1}][j_{k+1}] > A[i_k][j_k] \)
• The cell \( (i_{k+1}, j_{k+1}) \) is adjacent to \( (i_k, j_k) \); that is, it differs by exactly one row or one column.

Your solution should read the input from stdin and print the result to stdout.

inputFormat

The first line of input consists of two integers \( m \) and \( n \), representing the number of rows and columns of the matrix respectively.

This is followed by \( m \) lines, each containing \( n \) space-separated integers which represent the rows of the matrix.

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