TopCoder problem "LakeDepth" used in TCO04 Finals (Division I Level One)



Problem Statement

    Given the elevations of a plot of land, determine the deepest lake that could exist on the plot. Assume that water will flow off the edge of the plot, and therefore a lake will not cover any land on the border. A lake could form at a location up to level h so long as there is no path of horizontal or vertical steps from the lake to the edge of the plot that is completely below h. For example, consider the following plot:

  5255
  5225
  5525
  5515
  5555
A lake will form up to level 2 where the 1 is.



You will be given a String[], plot, where the ASCII value of plot[i][j] represents the height of the land at location (i,j). Your task is to determine the deepest lake that could form in the plot, where the depth of a lake is the largest difference between the lake height and the height of the land under the water.
 

Definition

    
Class:LakeDepth
Method:depth
Parameters:String[]
Returns:int
Method signature:int depth(String[] plot)
(be sure your method is public)
    
 

Notes

-If no lake can form, return 0.
 

Constraints

-plot will contain between 3 and 50 elements, inclusive.
-Each element of plot will contain between 3 and 50 characters, inclusive.
-Each element of plot will be the same length.
-Each character in plot will have an ASCII value between 32 and 126, inclusive.
 

Examples

0)
    
 {"5255",
  "5225",
  "5525",
  "5515",
  "5555"}
Returns: 1
This is the example above.
1)
    
 {"55555",
  "59995",
  "59595",
  "59195",
  "59995",
  "55555"}
Returns: 8
A lake of height '9' will form in the center of this plot.
2)
    
 {"55555",
  "59995",
  "59A95",
  "59A95",
  "59995",
  "55555"}
Returns: 0
No lake may form here, as 'A' has a higher value that '9'.
3)
    
{"55555",
 "52335",
 "53315",
 "45555"}
Returns: 4

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3101

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5886&pm=3101

Writer:

lars2520

Testers:

PabloGilberto , lbackstrom , Yarin , legakis

Problem categories:

Graph Theory