ŽUPANIJSKO NATJECANJE 2014. / Srednja škola, II. podskupina (3. i 4. razred) - 2. zadatak

Popularna računalna igra Tetris se igra u polju koje se sastoji od jediničnih kvadratića organiziranih u \(S\) stupaca i nema ograničenu visinu. Svaki kvadratić polja je ili prazan ili zauzet. U pojednostavljenoj verziji igre koju ćemo razmatrati u ovom zadatku, u svakom koraku se ubacuje u polje figura koja se sastoji od četiri jedinična kvadratića poredana u jednom stupcu jedan ispod drugoga.

Figuru možemo ubaciti u bilo koji stupac. Jednom kada se odabere stupac, figura pod djelovanjem gravitacije pada sve dok se ne smjesti na dnu polja ili na već zauzetom kvadratiću. Za razliku od originalne igre, figura se ne može rotirati niti pomicati lijevo ili desno prilikom padanja.

Kada se figura smjesti odnosno završi s padanjem, tada se iz polja za igru uklanjaju svi potpuno popunjeni redci.

Tako, na primjer, Slika \(3\) prikazuje tijek jedne igre. Nakon što ubacimo jednu figuru u drugi stupac te jednu figuru u peti stupac dva retka postaju potpuno popunjena te ih brišemo iz polja za igru.

Zadana je ploča za igru na kojoj su neki kvadratići već popunjeni. Napišite program koji će pronaći neki niz koraka koji će očistiti cijelu ploču osim eventualno zadnja tri redka. Drugim riječima, nakon izvođenja toga niza koraka svi kvadratići ploče koji su zauzeti se (ako postoje) moraju nalaziti u najdonja tri redka.

Pronađeni niz poteza ne treba nužno biti minimalan ali se ipak treba sastojati od najviše \(10000\) poteza.

Još jednom, smatramo da ploča za igru ima neograničenu visinu te se, dakle, u svakom koraku figura može ubaciti u bilo koji stupac. Ulazni podaci opisuju izgled \(R\) najdonjih redaka polja za igru na početku igre, te pretpostavljamo da su tada u ostalim redcima svi kvadratići prazni. Dozvoljeno je da tijekom igre budu zauzeti kvadratići i iznad ovih zadanih \(R\) najdonjih redaka.

Ulazni podaci

U prvom redu nalaze se dva prirodna broja \(R\) i \(S\) \((4 \leq R, S \leq 10)\), broj najdonjih redaka polja koje opisujemo te broj stupaca od kojih se polje za igru sastoji. U sljedećih \(R\) redaka nalazi se po \(S\) znakova koji opisuju početno stanje igre, gdje je znakom . označeno prazno polje, dok je malim slovom x označeno zauzeto polje.

Izlazni podaci

U prvi red potrebno je ispisati prirodan broj \(N\) manji ili jednak \(10000\) – broj koraka u vašem rješenju, a zatim u svaki od sljedećih \(N\) redova po jedan prirodni broj \(X_K\) \((1 \leq X_K \leq S)\), redni broj stupca u koji treba ubaciti figuru u \(K\)-tom potezu.

Stupci su označeni brojevima od \(1\) do \(S\) s lijeva na desno.

Napomena: Rješenje ne mora biti jedinstveno.

Primjeri test podataka

Ulaz

4 5 
..x..
x.xx.
..x..
x.xx.

Izlaz

2
2
5

Ulaz

4 7
.....x.
.x...x.
.....x.
..x.xx.

Izlaz

6
1
4
7
3
5
2