Alice in the Hills

3.1

9 votes
Dynamic Programming, Algorithms, 2D dynamic programming, Data Structures
Problem

Alice visited a hill with various mountains. The hill is present in the form of a 2-D square matrix A where each element denotes the height of the mountain. Alice can start from any mountain and jump to any mountain which lies on the same line as the current mountain, either vertically or horizontally.

A jump can be made only if the destination has a height smaller or equal to the current mountain he is standing upon. Alice wonders what is the maximum number of mountains he can visit jumping in the hills if he is allowed to start from any mountain.

Input

The first line of each test case contains two space-separated integers M and N — the number of rows and columns in the grid respectively.

The next M lines contain N space-separated integers, which are the entries in each row.

Output

Return a single integer denoting the maximum number of mountains he can visit in the hills in a new line.

Problem Constraints

1N,M103

1A[i][j]109

N=M

Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

One possible way is to start from (3,1). The path followed by Alice would be (3, 1)  -> (3,2)  -> (3,2) -> (3,3)  -> (2,3) -> (1,3)  -> (1,2).

 

Editor Image

?