Thanks to Simon who brought initial idea of this problem, to Graeme who hinted that simple version of it is too simple :) and to Alexandr who helped to fix the checker.
The Great Flood is mentioned in various religious and epic sources. Rain was so heavy that water level raised and covered even the highest peaks. After rain stopped and water had gone, the survivors found themselves on the top of the Mount Ararat (in modern Armenia).
As mountain has complicated shape with valleys and crevices, some water may remain in such deep places, in a manner of lakes.
We are given planar map of the mountain as a grid of heights. Suppose every grid cell is 1 furlong long and wide and heights are also given in furlongs. The question is, how many cubic furlongs of water is retained.
Formal description of process by which water flows off the mountain is a bit difficult to produce in details, so it is expected some intuition is plugged in and the following basic ideas:
Input gives the size of grid in the first line (single number as grid is square).
Next the grid itself follows, N lines of N positive integer values.
Output should have single integer value - amount of water.
Example:
input data:
6
9 9 9 9 9 9
9 6 5 1 3 9
9 2 9 9 4 9
3 4 9 9 7 9
9 9 9 9 4 9
9 9 9 9 5 9
answer:
14
Explanation: below is the same grid with heights of water surface marked with brackets:
9 9 9 9 9 9
9 6 [6][6][6] 9
9 [4] 9 9 [6] 9
3 4 9 9 7 9
9 9 9 9 [5] 9
9 9 9 9 5 9