A Garden with Ponds
Time limit2sMemory limit512 MB
Given a small elevation grid, find the rectangular pond whose border cells all exceed its interior cells, maximizing the total water it can hold.
- Level
Medium6 of 10
- Topics
- Brute force, Implementation, Array, Simulation
- Solved
- No attempts yet
Problem
Mr. Gardiner designs gardens that keep the existing terrain. He decides where the ponds go first, then designs each pond around the terrain as it is.
Every pond he builds is rectangular. He draws a regular grid over the map of the garden site so that the land is divided into unit square cells, and he writes the elevation of every cell on the map. A pond occupies a rectangular area of cells, and each of its outermost cells has to be higher than every one of its inner cells. In the grid map below the numbers are elevations, and a pond can occupy the shaded area. The outermost cells are shaded darker and the inner cells lighter. The elevations of the outermost cells are at least three and those of the inner cells are at most two.

A rectangular area that holds a pond must have at least one inner cell, so both its width and its depth are at least three.
When you pour water into an inner cell of a pond, the pond keeps the water until the level reaches the lowest of its outermost cells. Pour more and the water spills over. The capacity of a pond is the maximum amount of water it can keep, and a larger capacity is better. For the shaded area above the capacity is , where 3 is the lowest elevation among the outermost cells and 1, 0, 2 are the elevations of the inner cells. Given a grid map with the elevation of each unit square cell, compute the largest capacity of a pond that can be built on the site.
Neither of the two rectangular areas below can be a pond. In the left one the cell at the bottom right corner is not higher than the inner cell. In the right one the central cell is as high as the outermost cells.

Input
The input consists of at most 100 datasets, each in the following format.
d w
e(1,1) ... e(1,w)
...
e(d,1) ... e(d,w)
The first line holds and , the depth and the width of the garden site drawn on the map. Both are integers between 3 and 10, inclusive. Each of the next lines holds integers between 0 and 9, inclusive, separated by single spaces. The -th integer on the -th of those lines is the elevation of the unit square cell at coordinates .
The end of the input is a line holding two zeros separated by a space.
Output
For each dataset, print one line with the largest capacity of a pond that can be built on the garden site of that dataset. If no pond can be built, print 0.