Skiing on Mountains Matrix

Skiing on Mountains Matrix : “John Snow” likes Skiing on Mountains a lot.That’s not very surprising, since skiing is really great. The problem with skiing is one have to slide downwards to gain speed. Also when reached the bottom most point one has to wait for ski-lift to get to higher altitude.
“John Snow” seeks your help to know the longest run possible with the given peaks, As (“John Snow knows nothing” ), That altitude of different peaks is given by a grid of numbers. Look at this example Skiing on Mountains Matrix Path:

One can ski down from one peak to a connected peak if and only if the height decreases. One peak is connected to another if it’s at left, at right, above or below it. In the sample map, a possible ski path would be 36-33-24(start at 36, end at 24). Of course if one would ski 46-44-43-42-41-30-9….3-2, it would be a much longer run. In fact, it’s the longest possible. There could be more than one longest ski path, but all John Snow needs from you is to tell maximum number of peaks he could cover for a given map, in this case it is 14.

Input
All input comes from input.txt file. The first line contains the number of test cases N. Each test case starts with a line containing the name (it’s a single string), the number of rows R and the number of columns C. After that follow R lines with C numbers each, defining the heights. R and C won’t be bigger than 100.

Output
For each test case, print a line to output.txt containing the name of the area, a colon, a space and the length of the longest run (maximum points covered) one can slide down in that area.

Sample Input Skiing on Mountains Matrix
2
Alps 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

Great-Wall  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

Sample Output

Alps: 7
Great-Wall: 25

Here is the solution of this problem, Let me explain the algorithm first before proceeding for programming solution.

Algorithm :

1. Start from the first index of the row and go through one by one each index of the 2D grid.
2. For each node search in left, right, upper and lower side if any node which has less value than jump on that node, and add previous node(index) in the list to track the path, follow this for each side of node. you will get longest possible path for that node, for each side. Compare each path and select longest path from all four path, and add the location and path in map to track for next time.
3. Once done, means if didn’t find any more consecutive node(in left, right, upper and lower side), has less value than current node, than jump on the next node from where we started.
4. Do not revisit the same node if already visited, take the path from map.
5. Track the last longest path in list.
6. It will give you solution in O(n) complexity. you will visit each node once in the grid.

Can You try writing a Code for it ?