Loading...
Loading...
Loading...
The trekking club has a height map of a hill area: a grid of r rows and c columns, with the height of each square.
A rising walk starts on any square. Each step moves up, down, left or right to a square that is strictly higher than the current one. Diagonal moves are not allowed.
Print the number of squares on the longest rising walk.
Example 1
Input
3 3 9 9 4 6 6 8 2 1 1
Output
4
The walk 1 → 2 → 6 → 9 starts in the bottom middle, steps left to 2 and climbs the left column: 4 squares.
Example 2
Input
3 3 3 4 5 3 2 6 2 2 1
Output
4
The walk 3 → 4 → 5 → 6 has 4 squares. The two 3s next to each other cannot be used together.
Try the problem first. Open one hint at a time.
The longest walk starting at a square depends only on the walks starting at its higher neighbours.
So the answer for a square is 1 plus the best answer among its strictly higher neighbours. Many walks share the same squares, so save each answer once you have it.
If you handle the squares from highest to lowest, every higher neighbour already has its answer when you need it.
This is dynamic programming on the grid: sort the cells by height (descending), or use a depth-first search that saves each cell's answer (memoization).
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor