RiverHill
TCI '02 Round 3 · 2002-10-23 · by chogyonim
Problem Statement
A river can flow either downhill, or at a level elevation for a certain distance. Given a topographical map (a map representing elevations) and a maximum level flow distance, write a method to determine the largest area that a river can cover, if it starts at any location on the map.
The map will be a
The maximum level flow distance, maxDist, will be the longest a river can travel on level ground. So if the distance is 0, a river must flow downhill. If the distance is 1, it can flow to 1 adjacent coordinate of the same altitude, in each direction, before it must flow downhill. If the distance is 2, immediately after flowing downhill (or from the starting point), the river can flow to any adjacent coordinate of the same altitude, and then once again to any coordinate adjacent to the new one and of the same altitude, before it must go down hill. For this calculation, the river flows in the 4 primary directions (north, south, east, and west). Notice that since a river will go in any direction it can, it's more of a "flood" than a "river". Thus when determining the area covered by a river starting at a certain point, you must find the area of all the points that can be reached following the above constraints.
For example: 0000000000 0111111110 0122222210 0123333210 0123443210 0123443210 0123333210 0122222210 0111111110 0000000000
Represents a peak with an elevation of 4.
If maxDist = 2 and the river starts flowing at the '*' then the river can cover an area of 16, shown by '~'.
~~~~~~~000 ~~*~~11110 ~~22222210 ~123333210 ~123443210 0123443210 0123333210 0122222210 0111111110 0000000000However this isn't the largest area. If the river starts flowing at the peak, then the river can cover the entire area of 100.
Notes
- The river can only flow north, south, east, and west in determining the maximum level flow distance.
- Each coordinate has an area of 1.
Constraints
- map will contain between 2 and 40 elements, inclusive.
- each element of map will contain between 2 and 40 characters, inclusive.
- each element of map will contain the same number of characters as every other element of map.
- each element of map will contain only the characters '0'-'9' inclusive. There will be no spaces.
- maxDist will be an integer between 0 and 10, inclusive.
{"0000000000"
,"0111111110"
,"0122222210"
,"0123333210"
,"0123443210"
,"0123443210"
,"0123333210"
,"0122222210"
,"0111111110"
,"0000000000"}
2
Returns: 100
By starting the river at the peak (in either position), the river will be able to flow over the whole mountain.
{"0000000000"
,"0111111110"
,"0122222210"
,"0123333210"
,"0123443210"
,"0123443210"
,"0123333210"
,"0122222210"
,"0111111110"
,"0000000000"}
1
Returns: 95
If you started at the northwest corner of the peak, the only spaces not reachable would be the 5 spaces diagonally southeast from the start.
{"0000000000"
,"0111111110"
,"0122222210"
,"0123333210"
,"0123443210"
,"0123443210"
,"0123333210"
,"0122222210"
,"0111111110"
,"0000000000"}
0
Returns: 9
By starting the river at the peak (at any of the four elevation 4 positions), the river will only be able to flow downward in the 4 main directions, thus it will be two straight streams, with an area of 9.
{"555505555"
,"555515555"
,"555525555"
,"555535555"
,"555545555"
,"555545555"
,"555555555"}
1
Returns: 11
5555~5555 5555~5555 5555~5555 5555~5555 55~5~5555 5~*~~5555 55~555555 One of the best rivers starts at the asterix (*).
{"5565236785012472"
,"3469912625904101"
,"5943545942017700"
,"9109166568720711"
,"6136079994373860"
,"4129136148916755"
,"2975832922074121"
,"4674050103662805"
,"2494729679116165"
,"1611964958059846"
,"2384128690120444"
,"1010697089697114"
,"0089682613597732"
,"4971774663111966"
,"8543141293776080"
,"4298494798935152"
,"5202757354375791"
,"5376161470010537"
,"5696381123743171"
,"1446566116127226"}
2
Returns: 32
One of the best rivers (possibly uniquely the best) starts at the space on the 4th row, 6th column (both 0-indexed). The method returns 32.
Submissions are judged against all 50 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RiverHill with a public method int largest(vector<string> map, int maxDist) · 50 test cases · 2 s / 256 MB per case