DWITE '08 R2 #5 - Water damage

View as PDF
Submit solution
Points: 7
Time limit: 1.0s
Memory limit: 64M
Problem type
DWITE Online Computer Programming Contest, November 2008, Problem 5

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 a 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 will contain 5 sets of input. First line is an integer W, amount of water expected. Second line is an integer C, number of columns in a map. Third line is an integer R, number of rows in a map. Next R lines describe the layout of the area. 1 \le C, R \le 10. 1 \le W \le 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 1; it should be treated as empty space, but only this area counts for points. Each set is separated by a whitespace line.

The output will contain 5 lines, the number of points of interest underwater.

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 \times R=3 layout. Asterisk * represents a moving unit of water. 2nd 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

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

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

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

Sample Output

1
1
2

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments


  • 0
    maxcruickshanks  commented on Feb. 5, 2023, 2:00 a.m.

    Since the data were split by spaces instead of newlines, the data were updated, and all submissions were rejudged.


  • 0
    sp1cykumar  commented on April 27, 2018, 6:40 p.m.

    Note for some people getting IR, there is leading whitespace before each water value starting from set 2 onwards.