UVa 10285

From Algorithmist
Jump to navigation Jump to search

UVa 10285 - Longest Run on a Snowboard[edit]

Summary[edit]

Given a matrix of heights, we are to find the longest decreasing heights sequence starting from any cell. The matrix can be traversed left, right, up, or down remained inside.

Explanation[edit]

This problem can be solved by backtracking. For each cell, lengthen the sequence recursively to every possible direction until the deepest level is reached (i.e. no more possible direction to go). Record the maximum length encountered.

Optimizations[edit]

There is no need to backtrack for a cell which has been already checked. Use memoization to prevent extra recursive calls.

Input[edit]

3
Feldberg 10 5
56 14 51 58 88
26 94 24 39 41
24 16 8 51 51
76 72 77 43 10
38 50 59 84 81
5 23 37 71 77
96 10 93 53 82
94 15 96 69 9
74 0 62 38 96
37 54 55 82 38
Spiral 5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
testing 10 10
12 74 18 27 16 28 47 61 28 37
18 47 26 38 29 74 62 83 91 74
182 64 28 37 28 37 28 39 47 26
17 64 92 74 82 73 13 84 91 47
19 47 19 47 29 47 1 4 1 4
19 47 1 43 12 47 19  47 1 28
18 47 216 38 27 36 18 437 1 1
18 4 1 2 3 81 4 1 47 1
49 2 4 1 4 1 4 1 4 1
1 84 71 64 28 46 1 47 1 47

Output[edit]

Feldberg: 7
Spiral: 25
testing: 9