Županijsko natjecanje iz informatike 2018. / Prva podskupina (1. i 2. razred) - 2. 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.

Vaš je zadatak za zadano stanje ploče, u koju su već ubačeni neki žetoni, odrediti postoji li potez kojim igrač na potezu pobjeđuje, te koji je to potez.

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 njegovog protivnika.

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

Ako igrač \(1\) ne može pobijediti u sljedećem potezu, ispišite broj \(-1\). Inače, za svaki od mogućih pobjedničkih poteza, u zaseban redak izlaznih podataka ispišite redni broj stupca u koji treba ubaciti žeton. Potezi, tj. odgovarajući stupci trebaju biti ispisani u rastućem poretku.

Primjeri test podataka

Ulaz

0000000
0200201
0100101
0110201
0220102
0112101

Izlaz

4
7

Objašnjenje

Ubacivanjem u \(4\). stupac igrač \(1\) ostvaruje niz od četiri svoja žetona dijagonalno, a ubacivanjem u \(7\). stupac ostvaruje niz od četiri svoja žetona u tom stupcu okomito.

Ulaz

0000000
0000000
1000000
1010021
2022021
2112212

Izlaz

-1