2019 ICPC NENA (Quebec) Regional Qualifier

Start

2019-10-26 13:00 UTC

2019 ICPC NENA (Quebec) Regional Qualifier

End

2019-10-26 19:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -159 days 21:59:06

Time elapsed

6:00:00

Time remaining

0:00:00

Problem C
Decreasing Paths

Imagine you are on a large grid of square steps, where each step is at a different height, labeled by an integer. Starting from some step, you can move to any one of its $8$ orthogonal or diagonal neighbors that is a lower height than the current step – in other words, is labeled by a strictly smaller integer. You want to find the length of the longest strictly-decreasing path through this grid, starting at any step.

Input

Each input starts with a pair of numbers $r$, $c$ representing the number of rows and columns in the grid, where

\[ 1 \leq r,c \leq 256. \]

This is followed by $r$ rows of $c$ integers representing the heights of the steps in the grid, with columns separated by spaces. Each integer $x$ in the grid will be in the range

\[ -(2^{30}) \leq x \leq 2^{30}. \]

Output

Your program should output the length of the longest strictly-decreasing path through the grid on a single line.

Sample Input 1 Sample Output 1
3 4
16 4 -32 7
22 -18 4 -17
8 25 6 429
6
Sample Input 2 Sample Output 2
6 6
0 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8
4 5 6 7 8 9
5 6 7 8 9 10
11