Thornhill Computer Club 2023 - December Contest - Problem 3

In the last chronological problem, the Elves were hard at work trying to find all of the mine's coal and mine it as fast as possible. After a long time of mining, the Elves notice that they are mining more coal than anywhere else in the world. Not wanting to provide lumps of coal to all the naughty children, the Elves start a worker's revolt throughout Santa's Arctic coal mine so they can reap the profits of selling all their valuably mined coal.

Wanting to get their revenge on Santa and his tyrannical working conditions, they plan to escape the coal mine and rob Santa of all the world's Christmas presents. After the elves beat and cripple Santa's royal guards stationed in the mines, they quickly realize a problem, how will they be able to climb to the top of Santa's coal mine. Luckily, the elves are master cartographers and have created a depth map for the entire mine system. With access to this map, which contains the depth at any coordinate throughout the mine. To prepare for the climb, the elves have gained access to all the basins within the coal mine and can start climbing from any of those locations. A basin is any location where all surrounding locations have a smaller depth.

Unfortunately for the elves, they have no money and to make a quick buck, they plan to carry all the leftover coal back up to the top of the mine, which they will sell when they get to Canada. From this extra weight, the elves want to avoid climbing as much as possible and want to find the longest path up the mine.

Starting from any basin in the mine, can you find the length of the longest path in which you decrease your depth with every move until you reach a point where you cannot move anywhere else?

If you are submitting in Python, it is recommended you submit in PyPy 3, with fast input

Input Specifications

The first line consists of two integers ~L~ ~(2 \le L \le 1000)~ and ~W~ ~(2 \le W \le 1000)~ representing the length and width of the mines.

The next ~L~ lines consist of ~W~ integers ~D_i~ ~(1 \le D_i \le 100,000)~ representing the depth at length ~L~ and width ~W~.

Output Specification

Output the length of the longest decreasing path.

Subtasks

Subtask 1 [30%]:

• 2 ~\le |L| \le 10~
• 2 ~\le |W| \le 10~

Subtask 2 [70%]:

• No further constraints

Sample Input 1

3 3
2 4 3
6 5 4
2 5 8

Sample Output 1

4

Explanation of Sample Output 1

To find the longest decreasing path, you start at the 6.

You move right to the 5, right again to the 4, and up to 3.

You then stop at three because all the surrounding depths are greater.

This is what that path looks like.

2 4 3

6 5 4

2 5 8

The path 6-5-4-3 has a length of 4.

Sample Input 2

4 5
2 4 5 2 1
1 5 7 2 3
4 5 2 1 4
4 6 4 5 3

Sample Output 2

5

Explanation of Sample Output 2

The longest decreasing path is 7-5-4-2-1.

2 4 5 2 1

1 5 7 2 3

4 5 2 1 4

4 6 4 5 3

This path has a length of 5.