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

Ads

View Answers

January 3, 2013 at 3:06 PM

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

Related Tutorials/Questions & Answers:

Ads

- Java Tutorials
- Java Code example
- Java Programming
- Java Beginners Examples
- Applet Tutorials
- Awt Tutorials
- Java Certification
- Interview Question
- Java Servlets Tutorial
- Jsp Tutorials
- Java Swing Tutorials
- JDBC Tutorial
- EJB Tutorials
- Java Server Faces (JSF) Tutorial
- WAP Tutorial
- Struts Tutorial
- JAXB Tutorial
- Spring FrameWork Tutorial
- SOA&Web Services Tutorials
- Bioinformatics Tutorials
- MySQL Tutorials
- JAVA DOM Tutorial
- XML Tutorial
- EAI Articles
- Many Programming Tutorials Links
- Tutorials Books
**Java Script Tutorial****Ajax Tutorial****Dojo Tutorials****Programming Books****Trainings****Flex****Ant****RDF**