Ram likes skiing 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.
Ram seeks your help to know the longest run possible with the given peaks. That altitude of different peaks is given by a grid of numbers. Look at this example:
7 2 3 4 5 36 37 38 34 6 33 44 46 40 7 24 43 42 41 8 35 32 47 30 9
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 Ram 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
2
Manali 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
Narkanda 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 Manali: 7 Narkanda: 25
public class SkiPath { private static Integer[][] peaks = {{7,2,3,4,5}, {36,37,38,34,6}, {33,44,46,40,7}, {24,43,42,41,8}, {35,32,47,30,9}};
private static Integer[][] lRun = {{1,1,1,1,1}, {1,1,1,1,1}, {1,1,1,1,1}, {1,1,1,1,1}, {1,1,1,1,1};
public static int calLongestRun(int i,int j){ int useLeft = -1; int useRight = -1; int useAbove = -1; int useBelow = -1;
if(isAllowed(i,j-1,i,j)) useLeft = 1 + calLongestRun(i,j-1); if(isAllowed(i,j+1,i,j)) useRight = 1 + calLongestRun(i,j+1); if(isAllowed(i-1,j,i,j)) useAbove = 1 + calLongestRun(i-1,j); if(isAllowed(i+1,j,i,j)) useBelow = 1 + calLongestRun(i+1,j); return max(useLeft,useRight,useAbove,useBelow); }
public static int max(int lr,int rr,int ar,int br){ int m=1; if(lr > m) m = lr; if(rr > m) m = rr; if(ar > m) m = ar; if(br > m) m = br; return m; }
public static boolean isAllowed(int x1,int y1,int x,int y){ boolean ret = false; if(x1 >= 0 && y1 >= 0 && x1 < 5 && y1 < 5){ if(peaks[x1][y1] < peaks[x][y]) ret = true; } return ret; }
public static void main(String[] s){ for(int i=0;i<5;i++){ for(int j=0;j<5;j++){ lRun[i][j] = calLongestRun(i,j); } }
int m = 1;
for(int i=0;i<5;i++){ for(int j=0;j<5;j++){ if(m < lRun[i][j]) m = lRun[i][j]; } }
System.out.println("Longest Run is : "+m); }
}
Output: 14