MCIPC Contest 1 P5 - Rainwater

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

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 1 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 N and columns 1 and N 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

1 \leq R, C \leq 1000

Input Specification

The first line of input will contain integers R and C separated by a space. Where R represents the amount of rows and C represents the number of columns the blueprint contains.

The next R lines of input will contain C 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.

  1. In the first image, it hasn't rained yet and the collector is empty.
  2. In the next image, it starts raining and the collector becomes saturated with water.
  3. In the last image, it stops raining and the collector drains the uncollectable water, leaving 9 units of water behind.

Comments

There are no comments at the moment.