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)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)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):
102- 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.