Hide

# Problem CDecreasing 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

CPU Time limit 1 second
Memory limit 1024 MB