Martingrove Collegiate Institute's (MCI) number one rival Michaelgrove Collegiate Institute (MCI) is trying to steal the TDSB environment award from Martingrove!
To do this, they will collect rainwater using assorted containers and supplement their water supply (not drinking water) using the rainwater.
One day you receive a very conspicuous letter in the mail, which just so happens to be the blueprints to Michaelgrove's rainwater collectors. You, being a very good samaritan decide to re-mail it to the proper recipient, not before making a photocopy of course. Out of pure curiosity and nothing more, you would like to know how much water the collectors could store after it rains.
From your learning at Martingrove you know that water will follow these rules in the blueprint:
- Water can only flow downwards, leftwards, and rightwards (not upwards).
- When it starts raining, rain will start flowing from the top edge of the blueprint, every
.
at row will contain water. - Water will saturate the blueprint, that is, any space with a
.
that can be reached from another square containing water will now contain water. - When it stops raining, water will start flowing again. If it can flow off the bottom, right, or left edge of the blueprint it is considered lost. All spaces filled with water at row and columns and will no longer contain water. Any spaces filled with water that can reach a
.
that no longer has water will also no longer contain water.
Constraints
Input Specification
The first line of input will contain integers and separated by a space. Where represents the amount of rows and represents the number of columns the blueprint contains.
The next lines of input will contain characters, where an X
represents a wall that can stop water, and a .
represents free space.
Output Specification
Output one integer, the amount of water that is stored after it rains.
Sample Input
7 7
X...X.X
X...X.X
XXXXX.X
X......
X.X.X.X
XXXXXXX
X.....X
Sample Output
9
Explanation for Sample
The following set of images uses a black square to represent a wall, a white square to represent an empty space, and a blue square to represent one unit of water.
- In the first image, it hasn't rained yet and the collector is empty.
- In the next image, it starts raining and the collector becomes saturated with water.
- In the last image, it stops raining and the collector drains the uncollectable water, leaving units of water behind.
Comments