Reservoir
InterviewTime limit1sMemory limit128 MB
Raise water from the pump across edge-adjacent cells of bounded height to the highest level that floods no tree, and report the flooded count.
- Level
Medium6 of 10
- Topics
- Shortest path, Heap, Graph
- Solved
- No attempts yet
Problem
Farmer Jozef wants to build a fish pond in a rectangular hollow on his land. He puts a pump at the lowest point of the hollow and fills it with water. Fruit trees grow on some cells, and he does not want any tree to end up under water. He will choose how much water to pump so that no fruit tree is flooded while the pond is as large as possible.
The land is a grid of unit cells. The pump can raise the water to any level you like. A cell is covered by water when it is connected to the pump through a path of edge-adjacent cells whose heights are all at most the water level (water flows only across shared edges, never across a shared corner). The pond is the set of covered cells.
Choose the water level so that no cell holding a fruit tree is covered and the number of covered cells is as large as possible. How large can the pond be?
Input
The first line contains two integers and (): the number of rows and columns of the plot.
Each of the next lines contains integers, each with absolute value at most , describing the cells row by row. The absolute value of a number is the terrain height of that cell. A negative number marks a cell where a fruit tree grows. The single marks the pump; it appears exactly once and sits at the lowest point. Water spreads only between cells that share an edge.
Output
Print one integer: the largest possible area of the pond (the number of covered cells).