Županijsko natjecanje 2018. godine za 3. i 4. razred Srednje Škole - 3. zadatak

"Connect Four" kombinatorna je igra dvaju igrača na okomitoj ploči sa šest redova i sedam stupaca, koja je na početku igre prazna, a tijekom igre u nju se ubacuju žetoni. Žeton se ubacuje u odabrani stupac ploče (ako u njemu ima slobodnih polja) i nakon ubacivanja žeton pada po tom stupcu do najnižeg slobodnog polja.

Na početku igre svaki igrač odabire boju svojih žetona. Tijekom igre, igrači naizmjence vuku poteze ubacujući žetone svoje boje. Cilj je svakog igrača ostvariti niz od četiri žetona svoje boje koji su uzastopni u redu, stupcu ili po dijagonali. Igra završava čim se to dogodi i odgovarajući igrač proglašava se pobjednikom.

Tijekom jedne igre, igračima je stigla pizza koju su naručili iz obližnje pizzerije, pa su odlučili igru završiti što prije. Dogovorili su se da će odigrati najkraći niz poteza koji će rezultirati pobjedom igrača 1, onoga koji je na potezu u trenutku dogovora. Vaš je zadatak za zadano stanje ploče pronaći taj niz poteza.

Napomena: test podatci bit će takvi da će pobjednički niz sadržavati najviše 7 poteza (brojeći poteze oba igrača).

ULAZNI PODACI

Ulaz se sastoji od šest redaka koji predstavljaju izgled ploče, redom od najvišeg do najnižeg reda. Svaki redak sadrži sedam znakova 0, 1 i 2 (bez razmaka). Znak 0 predstavlja prazno polje, znak 1 predstavlja žeton igrača na potezu, a znak 2 predstavlja žeton drugog igrača.

U skladu s gravitacijom, iznad praznog polja neće biti žetona. Na zadanoj ploči još nema pobjednika (ali ona možda i nije nastala naizmjeničnim potezima igrača).

IZLAZNI PODACI

Ispišite najkraći niz poteza koji završava pobjedom igrača 1. Niz treba biti ispisan kao niz znakova od '1' do '7' (bez razmaka) od kojih pojedini znak označava redni broj stupca u koji igrač koji je tada na potezu treba ubaciti svoj žeton. (Igrač 1 vuče prvi, igrač 2 drugi, igrač 1 treći potez itd.)

Ako traženih najkraćih nizova ima više, među njima treba ispisati onaj koji je leksikografski najmanji, tj. onaj koji sadrži najmanji prvi znak, a u slučaju jednakosti prvog znaka, onaj koji sadrži najmanji drugi znak, i tako dalje.

PRIMJERI TEST PODATAKA

ulaz

0000000
0200201
0100101
0110201
0220102
0112101

izlaz

4

ulaz

0000000
2000000
1000000
2012000
2021100
2121220

izlaz

677

ulaz

0000000
0000000
1000000
1010021
2022021
2112212

izlaz

131

Pojašnjenje prvog primjera: Ubacivanjem u 4. stupac igrač 1 ostvaruje niz od četiri svoja žetona dijagonalno i pobjeđuje. Pobjedu bi ostvario i ubacivanjem u 7. stupac, ali niz „4“ leksikografski je manji od niza „7“.

Pojašnjenje drugog primjera: Igrač 1 ubacuje u 6. stupac, nakon čega igrač 2 ubacuje u 7. stupac, čime omogućuje igraču 1 da ubacivanjem u 7. stupac ostvari vodoravni niz od četiri svoja žetona.

Pojašnjenje trećeg primjera: Niz „121“ nije ispravan jer bi u tom slučaju igrač 2 pobijedio nakon drugog poteza.