DWITE '08 R2 #5 - Water damage

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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, an integer number of points of interest under water.

Technical details: Water originates at 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

Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


Comments


  • 1
    sp1cykumar  commented on April 27, 2018, 2:40 p.m.

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


  • 1
    w1rooo  commented on Nov. 16, 2017, 9:53 p.m.

    Keep getting IR, might be my program, but since I'm the only submission so far, could be with the tests


    • 1
      kipply  commented on Nov. 16, 2017, 11:26 p.m. edit 2

      Turns out there's an error with the sample cases. There are no empty lines between the five sets of input (and yes it's five inputs). Should be updated now~


    • 0
      insect  commented on Nov. 16, 2017, 11:25 p.m.

      There are 5 inputs not 3