Longest Increasing Path in a Matrix

You are given a two-dimensional matrix (A) with (n) rows and (m) columns containing integer values. Your task is to find the length of the longest increasing path in the matrix. From any cell (A[i][j]), you may move in one of the four directions: up, down, left, or right. A move is valid if and only if the target cell contains a strictly greater value than the current cell.

Note that the path does not need to be contiguous in value; however, every move must be to an adjacent cell in one of the four directions.

Formally, find the maximum length of a sequence of cells ((i_1,j_1), (i_2,j_2), \ldots, (i_k,j_k)) such that for every (1 \leq t < k), (i) the cell ((i_{t+1}, j_{t+1})) is adjacent to ((i_t, j_t)) (i.e. (|i_{t+1}- i_t|+|j_{t+1}- j_t| = 1)), and (ii) (A[i_{t+1}][j_{t+1}] > A[i_t][j_t]).

inputFormat

The input is read from standard input.

The first line contains two integers (n) and (m) representing the number of rows and columns in the matrix respectively. If either (n) or (m) is 0, the matrix is considered empty.

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

outputFormat

Output a single integer to standard output indicating the length of the longest increasing path in the matrix.## sample

3 3
9 9 4
6 6 8
2 1 1

4