Problem G
Where's My Waterfall?
As a level designer for Super Mawio Bros, you have been creating maps for Mawio to play on, each with some combination of blank spaces, bricks, and item boxes for Mawio to navigate on his way to save Princess Pweach. You want to make some of the maps more interesting, so you decide to add some waterfalls to them. These waterfalls naturally cascade around the bricks and item boxes that you have already placed as they flow down from the top of the screen.
Currently, the map contains nothing but bricks, item boxes, and blank spaces. Waterfalls will be placed at certain column numbers at the top of the screen. Given this information, output an updated map with the waterfalls displayed. Water flows straight down unless it is obstructed by a brick or item box. When water is obstructed by an obstacle, it will flow to both the right and the left of each obstacle, unless those locations are also obstructed. When water flows to the bottom of the map, it stops flowing at the spot it hits the bottom at.
In the current representation of the map, blank spaces are represented by the character ‘O’, bricks by the character ‘#’, and item boxes by the character ‘?’. In the updated representation, water should be represented by the character ‘$\sim $’. There will be no bricks nor item blocks on the top layer of a level.
Input
The first line containing three space separated integers
$n$, $m$, and $k$ ($1
\leq n,m \leq 1\, 000$, $1
\leq k \leq m$). $n$ and $m$ represent the number of rows and
columns in the map respectively. $k$ represents the number of
waterfalls that are to be added.
The second line contains $k$ space-separated integers with each
integer representing the column position $p_ k$ ($0 \leq p_ k < m$) of a waterfall
that needs to be added at the top of the map.
The next $n$ lines each
contain $m$ characters.
These $n$ lines represent
the $n \times m$ map of
the level. Blank spaces are represented by the character ‘O’,
bricks by the character ‘#’, and item boxes by the character
‘?’.
Output
Output $n$ lines with each line containing $m$ characters. These lines should represent a map that is updated to show the paths of the waterfalls, where water is represented by the character ‘$\sim $’.
| Sample Input 1 | Sample Output 1 |
|---|---|
8 20 3 2 9 15 OOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOO?OOOOO OOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOO###OOOO OOOOOOOOOOOOOOOOOOOO OOOOOOOOO##O?#O#?O## OOOOOOOOOOOOOOOOOOOO #################### |
OO~OOOOOO~OOOOO~OOOO OO~OOOOOO~OOOO?~OOOO OO~OOOOOO~OO~~~~~OOO OO~OOOOOO~OO~###~OOO OO~OOOOO~~~~~~~~~~OO OO~OOOOO~##~?#~#?~## ~~~~~~~~~~~~~~~~~~~~ #################### |
| Sample Input 2 | Sample Output 2 |
|---|---|
8 20 1 14 OOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOO?OOOOO OOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOO###OOOO OOOOOOOOOOOOOOOOOOOO OOOOOOOOO##??#O#?O## O########OOOOOOOOOOO #OOOOOOOOOOOOOOOO### |
OOOOOOOOOOOOO~~~OOOO OOOOOOOOOOOOO~?~OOOO OOOOOOOOOOOO~~~~~OOO OOOOOOOOOOOO~###~OOO OOOOOOOO~~~~~~~~~~OO ~~~~~~~~~##??#~#?~## ~########OOOOO~O~~~~ #OOOOOOOOOOOOO~O~### |
