Problem C
Fontän

Du får givet ett rutnät med $N$ rader och $M$ kolumner där varje cell är antingen luft, sten, eller vatten. Varje sekund sprider sig vattnet på följande sätt:

1. Om en vattencell har en luftcell direkt under sig så blir luftcellen till vatten nästa sekund.

2. Om en vattencell har en stencell direkt under sig så blir eventuella luftceller direkt till höger och vänster om vattencellen till vatten nästa sekund.

Efter ett antal sekunder så kommer vattnet ha slutat sprida sig. Skriv ut hur rutnätet ser ut då. Du kan anta att celler utanför rutnätet beter sig som luftceller, så till exempel om det är en vattencell längst ner i rutnätet så sprids inte vattnet åt sidan.

Indata

Den första raden innehåller två heltal $N$ och $M$ ($2\le N,M\le 50$), antalet rader och kolumner i rutnätet.

Var och en av de följande $N$ raderna innehåller en sträng $S$ av längd $M$. $S$ representerar en av raderna i rutnätet. $S$ kommer bestå av tecknen “.” (luft), “#” (sten) och “V” (vatten).

Utdata

Skriv ut $N$ stycken strängar av längd $M$, en kopia av rutnätet som det ser ut efter det att vattnet har slutat sprida sig.

5 7
...V...
.......
.......
...#...
..###..

...V...
...V...
..VVV..
.VV#VV.
.V###V.

12 14
....V...V.....
..............
..............
..............
...#########..
.......#......
.......#.#....
.......#####..
........###...
........#.#...
........#.#...
##############

....V...V.....
....V...V.....
....V...V.....
..VVVVVVVVVVV.
..V#########V.
..V....#....V.
..V....#.#..V.
..V....#####V.
..V.....###.V.
..V.....#.#.V.
VVVVVVVV#.#VVV
##############