Connection Status:
Competition Arena > LakeDepth

LakeDepth

TCO04 Finals · 2004-09-07 · by lars2520

TCO04 Finals · 2004-09-07 · by lars2520 · Graph Theory
Class Name: LakeDepth
Return Type: int
Method Name: depth
Arg Types: (vector<string>)
Problem Statement

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.

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)
{"asdkl;jhbgdsapo834ytwproiuenbvdflkuhg3908hbhg;sdlk",
 "4p9uihbnrtews;o84yht43q;puitbe;piughbv4we3['tih3e4",
 "4p9uihbnrtews;o84yht43q;puitbe;piughbv4we3['tih3e4",
 "4p9uihbnrtews;o84yht43q;puitbe;piughbv4we3['tih3e4",
 "4p9uihbnrtews;o84yht43q;puitbe;piughbv4we3['tih3e4",
 "4p9uihbnrtews;o84yht43q;puitbe;piughbv4we3['tih3e4",
 "4p9uihbnrtews;o84yht43q;puitbe;piughbv4we3['tih3e4",
 "4p9uihbnrtews;o84yht43q;puitbe;piughbv4we3['tih3e4",
 "4p9uihbnrtews;o84yht43q;puitbe;piughbv4we3['tih3e4",
 "4p9uihbnrtews;o84yht43q;puitbe;piughbv4we3['tih3e4",
 "4p9uihbnrtews;o84yht43q;puitbe;piughbv4we3['tih3e4",
 "pe498hgerp9ihge34w[o8hs[-0te34woighvnera;oibge4w3;",
 "pe498hgerp9ihge34w[o8hs[-0te34woighvnera;oibge4w3;",
 "pe498hgerp9ihge34w[o8hs[-0te34woighvnera;oibge4w3;",
 "pe498hgerp9ihge34w[o8hs[-0te34woighvnera;oibge4w3;",
 "pe498hgerp9ihge34w[o8hs[-0te34woighvnera;oibge4w3;",
 "pe498hgerp9ihge34w[o8hs[-0te34woighvnera;oibge4w3;",
 "pe498hgerp9ihge34w[o8hs[-0te34woighvnera;oibge4w3;",
 "pe498hgerp9ihge34w[o8hs[-0te34woighvnera;oibge4w3;",
 "pe498hgerp9ihge34w[o8hs[-0te34woighvnera;oibge4w3;",
 "pe498hgerp9ihge34w[o8hs[-0te34woighvnera;oibge4w3;",
 "pe3hgte34wohgte349ht23wujt-ujt3wsugtehngvero;n bvf",
 "pe3hgte34wohgte349ht23wujt-ujt3wsugtehngvero;n bvf",
 "pe3hgte34wohgte349ht23wujt-ujt3wsugtehngvero;n bvf",
 "pe3hgte34wohgte349ht23wujt-ujt3wsugtehngvero;n bvf",
 "pe3hgte34wohgte349ht23wujt-ujt3wsugtehngvero;n bvf",
 "pe3hgte34wohgte349ht23wujt-ujt3wsugtehngvero;n bvf",
 "pe3hgte34wohgte349ht23wujt-ujt3wsugtehngvero;n bvf",
 "pe3hgte34wohgte349ht23wujt-ujt3wsugtehngvero;n bvf",
 "pe3hgte34wohgte349ht23wujt-ujt3wsugtehngvero;n bvf",
 "pe3hgte34wohgte349ht23wujt-ujt3wsugtehngvero;n bvf",
 ";oijhbt32p49uhtgerlkjngvsa;dlkj398yr32poiuthger;lj",
 ";oijhbt32p49uhtgerlkjngvsa;dlkj398yr32poiuthger;lj",
 ";oijhbt32p49uhtgerlkjngvsa;dlkj398yr32poiuthger;lj",
 ";oijhbt32p49uhtgerlkjngvsa;dlkj398yr32poiuthger;lj",
 ";oijhbt32p49uhtgerlkjngvsa;dlkj398yr32poiuthger;lj",
 ";oijhbt32p49uhtgerlkjngvsa;dlkj398yr32poiuthger;lj",
 ";oijhbt32p49uhtgerlkjngvsa;dlkj398yr32poiuthger;lj",
 ";oijhbt32p49uhtgerlkjngvsa;dlkj398yr32poiuthger;lj",
 ";oijhbt32p49uhtgerlkjngvsa;dlkj398yr32poiuthger;lj",
 " tgp4398 4oiu3h t4398 yt3498y 43oih tpi4h t4p83y t",
 " tgp4398 4oiu3h t4398 yt3498y 43oih tpi4h t4p83y t",
 " tgp4398 4oiu3h t4398 yt3498y 43oih tpi4h t4p83y t",
 " tgp4398 4oiu3h t4398 yt3498y 43oih tpi4h t4p83y t",
 " tgp4398 4oiu3h t4398 yt3498y 43oih tpi4h t4p83y t",
 " tgp4398 4oiu3h t4398 yt3498y 43oih tpi4h t4p83y t",
 " tgp4398 4oiu3h t4398 yt3498y 43oih tpi4h t4p83y t",
 " tgp4398 4oiu3h t4398 yt3498y 43oih tpi4h t4p83y t",
 " tgp4398 4oiu3h t4398 yt3498y 43oih tpi4h t4p83y t",
 "fr4iojng 43598th43iu ht43qp98 yt4398y t34q htpoeh4"}
Returns: 72
4)
{"]]]","] ]","]]]"}
Returns: 61
46)
{
"5vVE;",
"sfk2L",
"Ql$@6"}
Returns: 14

{ "q4|J5vVE;", "%^BBsfk2L", "AB7'Ql$@6"}

Submissions are judged against all 77 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LakeDepth with a public method int depth(vector<string> plot) · 77 test cases · 2 s / 256 MB per case

Submitting as anonymous