Problem Statement
We will model the terrain using a grid of hexagons, each of which has a constant height. The surrounding area is lower than any of the hexagons. When water flows from a level area the flow is evenly distributed among all the edges that it flows over. The rain is falling at a rate of 1 foot per hour per square foot of horizontal area.
Here is an example showing a grid with 3 rows and 4 "columns" of hexagons. Consider the single cell area with height 4. Water continuously flows into it from 5 of its neighbors as well as directly from the rain. It all flows out to the cell with height 2. A more complicated area is the 2-cell area with height 10. This area gets water both from cell 13 (across 2 edges) and from rainfall onto itself. It has a total of 10 edges of which 8 have water flowing out. So 1/8 of the water coming into the area flows directly into the cell with height 2, and 1/8 of the water coming into the area flows directly into the cell with height 9 (some of which then also flows into the cell with height 2). The remaining 6/8 of the water flows into the lowlands.
Initially, all the rain either goes to the lowlands or to the cell at height 2. But eventually the water collecting at that cell will reach height 4 at which point there will be a lake covering those 2 cells. The water in the lake will continue to rise until it reaches height 8 at which point all additional rain will make its way to the lowlands.
11 12 13 10
8 4 2 10
9 10 8 9
String[] terrain contains the cell heights using the convention 'A'=1,'B'=2,'C=3',
etc., where the first element gives the heights from left to right in the top row of
hexagons and successive elements correspond to successive rows of hexagons arranged
as shown above.
My house is located in the cell whose row and column are given by hrow and hcol
and is ruined when the water in that
cell is 2.7 feet above the cell's height. Given terrain, hrow and hcol return
the number of hours before my house is ruined. Return -1.0 if it will never be ruined.
Definition
- Class:
- Flooding
- Method:
- ruinTime
- Parameters:
- String[], int, int
- Returns:
- double
- Method signature:
- double ruinTime(String[] terrain, int hrow, int hcol)
- (be sure your method is public)
Notes
- A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.
Constraints
- terrain will contain r elements, between 1 and 50, inclusive.
- Each element of terrain will contain c characters, between 1 and 50, inclusive.
- hrow will be beteen 0 and r-1, inclusive.
- hcol will be between 0 and c-1, inclusive.
Examples
{"KLMJ","HDBJ", "IJHI"}1
0
Returns: -1.0
This is the example above, with my house located on the cell with height 8. Since it borders the lowlands, water can never build up on it.{"JJJJ","JDDJ","JJJJ"}1
2
Returns: 1.1302325581395352
10 10 10 10 10 4 4 10 10 10 10 10 This has a high level outer ring which has 10 cells with 36 edges as its boundary, all of which drain to lower levels. Of the 36 edges, 10 drain to the inside area with height 4 and the others drain out to the lowlands. So of the 10 feet of rain per hour per square foot that falls on the outer ring, 10/36 of it flows into the central area. So the water in the central area rises at a rate of 1 foot per hour from the rain landing on it plus 10/36 * 10 spread over the area of 2 cells giving 1 + 100/72 feet per hour. The time until ruin is thus 2.7 / (172/72) = 1.1302325581395352.{"JJJJ","JDBJ","JJJJ"}1
1
Returns: 1.548837209302326
10 10 10 10 10 4 2 10 10 10 10 10 This is similar to the previous example except that at first all the water that doesn't drain into the lowlands goes into the single cell with height 2. After that one fills to a height of 4 there is a 2 cell lake and it takes 1.13023 more hours to get high enough to ruin our house, as calculated above. The time for the single cell to fill to a height of 4 can be calculated as (4.0-2.0) / (2+100/36) = .4186. So the amount of time until the house is ruined is 1.1302 + .4186 = 1.548837209302326.
Back to all problems