Razarač balona je igra za jednog igrača koja se igra na tabli dimenzije 15 x 15. Na svakom polju table se nalazi po jedan žeton koji može biti crvene, zelene, plave, žute ili ljubičaste boje (pet boja). Tablu ćemo posmatrati kao matricu dimenzije 15 x 15, gde je gornje levo polje sa koordinatama (1, 1). Žeton na polju (i , j ) je susedan sa žetonima na poljima (i+1 , j ), (i , j+1 ), (i-1, j), (i ,j-1 ), ukoliko ova polja pripadaju tabli. Grupa žetona je definisana kao skup dva ili više povezanih žetona iste boje (od svakog žetona je moguće dođi do svakog drugog žetona iz skupa preko gore opisane relacije susedstva).

Pod potezom se podrazumeva uklanjanje proizvoljne grupe žetona sa table, pri čemu dolazi do sledećih transformacija:

• vertikalna gravitacija: žetoni koji su iznad uklonjenih žetona "padaju dole"(slika)
• horizontalna translacija: ukoliko su nakon uklanjanja grupe žetona dobijene prazne kolone, sve neprazne kolone se transliraju levo, koliko je to moguće, pri čemu se očuvava njihov poredak (slika)

Na startu, igrač ima 0 poena. Za uklonjenu grupu od k ≥ 2 žetona, igrač dobija (k - 2)² poena. Kada više nije moguće povući potez (tabla je prazna ili ne postoji grupa od bar dva susedna žetona iste boje), igra se prekida. Nakon odigranog poslednjeg poteza, ukoliko je ostalo r žetona na tabli, od ukupnog broja poena oduzima se vrednost (r - 2)². Cilj igre je osvojiti što veći broj poena.

Za ovaj zadatak potrebno je predati izlazne datoteke za 10 ulaznih datoteka ''igra.01.in, 'igra.02.in, ..., ''igra.10.in, koji se nalaze u arhivi na računaru. Izlazi se pamte u dato- teke 'igra.01.out, 'igra.02.out, ..., 'igra.10.out, pri čemu broj u nazivu izlazne datoteke odgovara broju u nazivu ulazne datoteke.

Ulaz.

(Ulazni podaci se učitavaju iz datoteke igra.xx.in.) Ulazna datoteka sadži 15 redova od po 15 karaktera. Karakteri su mala slova engleskog alfabeta 'a', 'b', 'c', 'd' i 'e', koji označavaju boje žetona. Prvi karakter na ulazu označava boju žetona na polju (1, 1).

Izlaz.

(Izlazni podaci se ispisuju u datoteku igra.xx.out.) Prvi red izlaza sadrži prirodan broj m koji označava broj poteza. U narednih m redova treba štampati dva prirodna broja iz segmenta [1, 15] koji označavaju koordinate žetona čija se grupa uklanja u tom potezu (može se štampati koordinata bilo kog žetona iz grupe koja se uklanja). Prvi broj označava broj vrste, a drugi broj kolone (vrste su numerisane odozgo na dole, a kolone s leva na desno).

Bodovanje. Broj bodova za svaki test primer se određuje na sledeći način. Neka je P broj poena koje je vaša strategija osvojila, a OTP je maksimalna vrednost među svim takmičarskim rešenjima, uključujući i komisijsko rešenje. Ukoliko je je P ≤ 0, na tom test primeru dobijate 0 bodova. Inače, broj bodova koje dobijete se računa po formuli (zaokrugljivanje se vrši na najmanji ceo broj koji nije manji):

10²- OTP/P

Drugim rečima, ako je vaše rešenje identično sa najboljim dobijate 10 poena. U slučaju da je rešenje duplo manje (lošije) od najboljeg rešenja - dobićete 2 poena. Naravno, u slučaju da je odigran neki nelegalan potez (potez van table, uklanjanje nepostojeće grupe ili grupe sa samo jednim žetonom) na tom test primeru dobijate nula bodova.