Županijsko natjecanje 2014. godine za 1. i 2. razred Srednje Škole - 1. zadatak

Mirko je kao mali volio igru Boulder Dash u kojoj junak trči kroz podzemne hodnike sakupljajući dijamante i izbjegavajući kamenje. Vaš zadatak je da napišete program koji simulira dio te igre – padanje kamenja.

Ploča za igru je kvadratna mreža koja se sastoji od R redaka označenih brojevima od 1 do R odozgo prema dolje te S stupaca označenih brojevima od 1 do S s lijeva na desno. Svaki jedinični kvadratić u mreži je ili prazan (označen znakom ‘.’), ili na njemu može biti prepreka (označena znakom ‘#’) ili kamen (označen malim slovom ‘o’). Na početku igre ne postoji niti jedan kamen na ploči.

U svakom koraku se u neki stupac ubacuje točno jedan kamen koji se najprije pojavi u prvom retku tog stupca te dalje pada dolje kroz ploču prema sljedećim pravilima:

• Ako je polje neposredno ispod kamena prazno, onda kamen pada na to prazno polje.
• Ako se na polju neposredno ispod kamena nalazi prepreka ili se kamen nalazi u najdonjem redu ploče, onda kamen ostaje na mjestu te je korak gotov.

• Ako se neposredno ispod kamena nalazi drugi kamen, tada se događa sljedeće:

  • Ako su polja neposredno desno i dolje-desno od kamena koji pada prazna (te unutar ploče za igru), tada kamen propada na polje dolje-desno
  • Inače, ako su polja neposredno lijevo i dolje-lijevo od kamena koji pada prazna (te unutar ploče za igru), tada kamen propada na polje dolje-lijevo
  • Inače, kamen ostaje na mjestu te je korak gotov.

  

Na primjer, ako je trenutno stanje ploče kao na slici gore lijevo te kamen ubacujemo u četvrti stupac onda će on padati putanjom naznačenom brojevima na slici desno.

Napišite program koji će na temelju početnog izgleda ploče te zadanog niza koraka gdje je svaki korak ubacivanje kamena u jedan stupac, odrediti konačni izgled ploče nakon što je svo kamenje ubačeno

ULAZNI PODACI

U prvom redu nalaze se dva prirodna broja R i S (1 ≤ R, S ≤ 100), broj redaka i stupaca mreže kvadratića. U svakom od sljedećih R redova nalazi se niz od točno S znakova ‘.’ (točka), ‘#’ – izgled ploče na početku igre.

U sljedećem redu nalazi se prirodni broj K (1 ≤ K ≤ 100), broj kamenja koje ubacujemo u ploču.

U sljedećem redu nalazi se K prirodnih brojeva između 1 i S (uključivo) odvojenih jednim razmakom, redni brojevi stupaca u koje (u zadanom poretku) treba ubaciti kamenje.

Ulaz će biti takav da će uvijek u ploči biti mjesta za kamen koji se ubacuje. Drugim riječima, ako u nekom koraku treba ubaciti kamen u stupac A, tada će u tom trenutku prvi redak stupca A biti prazan.

IZLAZNI PODACI

Potrebno je ispisati R redova, u svaki red točno S znakova - izgled ploče za igru nakon što je svo kamenje ubačeno.

Ploča treba biti identična onoj s ulaza osim što na pozicijama na kojima se nalazi kamenje treba pisati malo slovo ‘o’.

PRIMJERI TEST PODATAKA

ulaz

5 7
.......
.......
.#.....
.#.#..#
.......
6
2 2 2 2 6 6

izlaz

.......
.o.....
.#o....
.#o#..#
..o.oo.

ulaz

5 6
......
......
...#..
......
......
7
4 4 4 4 3 4 5

izlaz

......
...o..
...#..
....oo
..oooo