Školsko natjecanje iz informatike 2019. / Prva podskupina (1. i 2. razred) - 3. zadatak

Figura u igri sličnoj Tetrisu pada na donji dio ekrana (gdje su već pale neke figure). Figura koja pada je „obrnuti histogram“, tj. sastoji se od nekoliko stupaca poravnatih s gornje strane. Ekran prikazujemo tablicom od \(R\) redova i \(S\) stupaca, pri čemu je polje figure predstavljeno znakom '#' (hash ili ljestve), a prazan prostor znakom '.' (točka). Zadan je izgled ekrana prije padanja figure, tako da se u gornjem dijelu ekrana nalazi figura, kao u sljedećem primjeru:

..###..
..##...
..#....
.......
......#
..#...#
#######

Prije nego što figura počne padati, igrač je može pomicati lijevo i desno, ali nakon što počne padati, igrač je više ne može micati. Čim neki dio figure padne na neko popunjeno polje donjeg dijela ekrana, figura prestaje padati. Za gornji primjer (bez prethodnog pomicanja figure lijevo ili desno) nakon pada figure rezultat je sljedeći:

.......
.......
..###..
..##...
..#...#
..#...#
#######

Prazna polja ekrana iznad kojih se nađe dio figure koja je upravo pala zovemo rupama. U ovom slučaju dobili smo pet rupa, dolje radi ilustracije označenih znakovima '*':

.......
.......
..###..
..##*..
..#**.#
..#**.#
#######

Da smo figuru prije pada pomaknuli sasvim desno, dobili bismo samo jednu rupu (dolje neoznačenu):

.......
.......
.......
....###
....###
..#.#.#
#######

Napišite program koji unosi izgled ekrana prije pada figure te ispisuje izgled ekrana s najmanjim mogućim brojem rupa nakon pada figure.

(Obratite pažnju na sekciju Bodovanje.)

Ulazni podaci

U prvom retku nalaze se prirodni brojevi \(R\) i \(S\) \((3 \leq R, S \leq 10)\), dimenzije ekrana.

U sljedećih \(R\) redaka nalazi se po \(S\) znakova iz skupa \({'.', '#'}\) koji opisuju izgled ekrana kao u tekstu zadatka, zadovoljavajući sljedeća svojstva:

• U gornjih nekoliko redaka nalazit će se figura, sačinjena od znakova \('#'\), koja će zauzimati dva ili više uzastopnih stupaca od kojih će svaki biti popunjen od prvog retka niže. Drugim riječima, svi stupci figure započinjat će u prvom retku i neće sadržavati „rupe“.

• Ispod figure nalazit će se barem jedan redak praznih polja, tj. znakova \('.'\) (točka).

• Svako popunjeno polje (znak \('#'\)), ako nije dio figure, bit će duž svog stupca povezan s donjim retkom ekrana, koji će biti cijeli popunjen. Tako ni u donjem dijelu ekrana neće biti „rupa“.

Izlazni podaci

Ispišite izgled ekrana nakon padanja figure s najmanjim brojem dobivenih rupa, u istom obliku i istih dimenzija kao u ulaznim podatcima (\(R\) x \(S\)), koristeći iste znakove. Dakle, dobivene rupe trebaju ostati prikazane točkama, tj. znakovima \('.'\) (u tekstu je korišten znak \('*'\) samo radi pojašnjenja).

Test podatci bit će takvi da će rješenje biti jedinstveno, tj. postojat će samo jedan položaj figure koji rezultira najmanjim brojem rupa.

Bodovanje

U test podatcima vrijednima \(50\%\) bodova figura će zauzimati sve stupce (cijelu širinu ekrana), što znači da je neće biti moguće micati lijevo ili desno (vidi prvi primjer ispod).

Primjeri test podataka

Ulaz

8 5
#####
.###.
..#..
.....
.....
..#..
.###.
#####

Izlaz

.....
.....
#####
.###.
..#..
..#..
.###.
#####

Ulaz

7 7
..###..
..##...
..#....
.......
......#
..#...#
#######

Izlaz

.......
.......
.......
....###
....###
..#.#.#
#######