teddy online judge

503. Like Water for Clay

Limite de tiempo : 1 seg.   Total runs : 1  Aceptados : 0

People do strange things. Recently, some folks have started building structures out of Stick-Tite blocks ("They stick ... tight!"), pressing them between two sheets of perspex, and dunking them in water.

Yeah, I don't know either.

Stick-Tite blocks are one inch cubes of some sort of material that is permeable to air but not water. They stick quite nicely to each other when properly aligned, such that it"s delightfully easy to make any sort of nice pixel-esque structure. They also stick well (but not too well) to perspex (also known as Plexiglas(tm)).

When dunked underwater and shaken about a bit, water fills the open space in a Stick-Tite construction such that any open spaces are filled unless they are completely enclosed inside the construction. While Stick-Tite blocks are water-impermeable, water can fill from any open space to any other open space that is orthogonally or diagonally adjacent.

X.. .X. ..X	Water can flow between the top-right and bottom-left areas
X.. XXX ...	Water cannot flow between the top-right and bottom-left areas

Consider the above two examples of such a construction. At the top, water can come through the blocks (represented by Xes) to fill the top chamber. At the bottom, water would not be able to flow between the two areas unless they were connected elsewhere.

After being dunked and wiggled, the Stick-Tite construction is pulled straight out of the water. Water drains out from any holes in the bottom or sides of the construction, coming out of all internal chambers and passages until the water level is even with the bottom of holes in the sides of chambers. In addition, due to static water pressure, the height of water in any pool still connected after this draining will never be higher than the bottom of the lowest hole that the pool"s water can flow from.

XXXXXXXXXXX
XX......XXX
XXX.XXXXX.X
X...X.XXXXX
X.X.X...X.X
X.X~X~X.X.X
X.X~~~X...X
X.XXXXXXX.X

In the above example, the tildes represent the maximum amount of water that the center pool can hold; while the left side has a hole one unit higher than the right side, the water level for the pool as a whole cannot be higher than the one on the right side. The act of draining pools may make a pool of water into smaller, separate pools; these would then drain independently.

XXXXXXXXXXX
X......X..X
X.XXXX~X..X
X.X~~~~X...
X~XXXXXX~~X
X~~~~~~X~~X
X~~~~~~~~~X
XXXXXXXXXXX

A particular Stick-Tite construction will hold different amounts of water depending on which direction it"s dunked into the bucket from. Given the blocks comprising a particular construction, you will determine how much water it can hold when dunked with each of its four edges facing straight up. (The construction is dried out completely between dunkings.)

Sample Input/Output

2
8 11
XXXXXXXXXXX
XX......XXX
XXX.XXXXX.X
X...X.XXXXX
X.X.X...X.X
X.X.X.X.X.X
X.X...X...X
X.XXXXXXX.X
8 11
XXXXXXXXXXX
X......X..X
X.XXXX.X..X
X.X....X...
X.XXXXXX..X
X......X..X
X.........X
XXXXXXXXXXX

31 5 4 1
40 25 24 10