Largest water storage pool
Given a matrix whose values show the height of that position, find the largest pool for storing water in the matrix. For example:
[0,1,0]
[1,0,1]
[0,1,0]
This can contain a 1 in the center because the values are higher, lower, left and right higher than the center value by one.
[0,2,0]
[2,0,2]
[0,2,0]
You can hold 2 in the center and
[0,2,0]
[2,0,2]
[0,1,0]
Can only contain one.
Another example is a matrix in the form
[0,2,2,0]
[2,0,1,2]
[0,2,2,0]
In this case, the largest pool size is 3 , because the two cells [0,1]
can store the maximum [2,1]
respectively so that it does not leak through the surrounding 2
cells, and the sum of the two cells is 3.
You can assume the matrix is an arbitrary NxM matrix
If the entrance
[1, 2, 78, 39, 20]
[4, 66, 17, 8, 55]
[35, 42, 78, 31, 64]
[34, 64, 24, 55, 21]
the result is 61 since 17, 8, 31 can add up to 39 without leaking.
You can subtract 17 8 31
from 39 because all the other values around this area are even greater or equal to 39. It's just that the image of the matrix is a map, and the whole number is the height ma. You can fill an area with water if you find that the area is below its surroundings.
In another way to explain this, you can have a pool of N adjacent indexed elements in the matrix, and the largest pool in this example is produced by adjacent numbers [17,8,31]
, because if you take the minimum adjacent one, which is 39 , then 39-17
, 39-8
and 39-31
, which is 22+31+8 = 61
, is the maximum value that can be stored in a given given pool, and this is the largest possible pool in the matrix.
How do I find the largest storage pool?
"Largest" is defined as the largest sum of all depths in the pool.
You should implement a function like:
public int findBiggestPool(int[][] matrix)
The question is similar to How to calculate the number of valleys in a sequence of numbers? but it is a matrix not an array
source to share
Ineffective but direct approach
Definitions
- Level - the height of the water.
- Overflow level - the maximum level that a cell can contain
- Depth - overflow level minus cell value
Algorithm
Find the overflow level for each cell:
- Create a level matrix with maximum value
- Set the levels of the border cells to their values.
- For each cell, set your level to the minimum level of neighbors, but not less than its value
- Repeat 3 until stabilized
Find pools:
- Take an unlabeled cell, set the pool volume to depth
- Recursively collect all unlabeled adjacent cells of the same level and positive depth, adding their depth to that and marking them
- Compare the pool volume with the previous volume leader, remember if the current is greater.
- If there are unlabeled cells goto 1
Homework:
- re-read cluster analysis books
- remove recursion
- merge steps
- reuse buffer
source to share
mark all outer cells as "leaky"
recursively mark all cells adjacent to a leaking cell as leaking if they are as tall or taller than leaking cells.
After that, all cells that are not checked are part of a viable pool - create collections of all interconnected pools (let's call these lakes).
The lake's water level is the height of the lowest oozing cell it touches.
The total volume of the lake is the sum of all positive values (water level - cell height)
Calculate all lake volumes and use the largest.
This also offers a nasty test case - make sure whatever algorithm you ended up with works when the largest pool contains an island. I can imagine several failures.
source to share