Longest Consecutive Path in a Matrix

Given an n × m matrix of integers, your task is to find the length of the longest path consisting of consecutive integers. A path is defined by moving from one cell to a neighboring cell in any of the four cardinal directions (up, down, left, right), where the value in the next cell is exactly equal to the current cell’s value plus one, i.e. \( a_{next} = a_{current} + 1 \).

For example, in the matrix below:

1 2 9
5 3 8
4 6 7

Starting from the cell with value 1, you can move to 2, then 3 and finally 4, achieving a path length of 4. If no consecutive neighbor is available, the path length is 1 for that starting cell. Your goal is to compute the maximum such consecutive sequence found anywhere in the matrix.

inputFormat

The first line contains two integers (n) and (m) denoting the number of rows and columns in the matrix. Each of the following (n) lines contains (m) integers separated by spaces representing the matrix rows.

outputFormat

Output a single integer representing the length of the longest consecutive path in the matrix.## sample

3 3
1 2 9
5 3 8
4 6 7

4