DWITE Online Computer Programming Contest
November 2008
Problem 5
Water damage

There's a shady water dam that might break, so an insurance company wants to calculate the possible damage given a series of scenarios. Given the topography of the region and the amount of water projected to spill out, the goal is to find out how many of the targets of interest will be submerged after the water settles.

The input file DATA5.txt will contain 5 sets of input. The first line is an integer W, the amount of water expected. The second line is an integer C, the number of columns in the map. Third line is an integer R, the number of rows in the map. The next R lines describe the layout of the area. 1 <= C, R <= 10. 1 <= W <= 100. Dot (.) is empty space that could be flooded. Number sign (#) is land. Capital letter A is a point of interest; there will be at least one; it should be treated as empty space, but only this area counts for points. Each set is separated by a whitespace line.

The output file OUT5.txt will contain 5 lines, the integer number of points of interest submerged under water.

Technical details: Water originates at the top left of the map. Each unit of water occupies one cell on the map. Water normally falls down. If there's ground below, it will move to the right. Once in place (can no longer flow), it could be treated as solid ground, as far as the movement of other units of water is concerned.

Step-by-step diagram: 2 units of water, C=4 × R=3 layout. Asterisk (*) represents a moving unit of water. The second unit of water reaches A at the bottom. Even though A at the top was passed by water, it remains un-submerged at the end, so it's not counted towards the output sum.

*.A. .*A. ..A. *.A. .*A. ..*. ..A* .... ..A. 
#.#. #.#. #*#. #*#. #*#. #*#. #*#. #*#* #*#. 
###A ###A ###A ###A ###A ###A ###A ###A ###* 
		  

Sample Input (first 3 shown):
2
4
3
..A.
#.#.
###A

4
4
3
..A.
#.#.
###A

5
4
3
..A.
#.#.
###A
		        
Sample Output:
1
1
2