Županijsko natjecanje 2015 / Osnovna škola (8. razred) - 2. zadatak

Daniel je kvartovski prvak u neobičnoj verziji poznate igre križić-kružić. Pravila njegove inačice su sljedeća. Igra se na tablici proizvoljne veličine s N redaka i M stupaca. U igri sudjeluje K igrača, a svaki od njih ima svoju jedinstvenu oznaku koja može biti jedno od prvih K slova engleske abecede.

Potezi igrača odvijaju se slično kao i u igri križić-kružić. Kada je igrač na potezu, on svoju oznaku zapiše na polje tablice koje još nije zauzeto, tj. na kojemu prethodno nije zapisana ni jedna oznaka. Igra završava nakon određenog broja poteza, a po završetku igračima se dodjeljuju bodovi. Igrač dobiva po jedan bod za svaki uzastopni niz od tri vlastite oznake u retku, stupcu ili nekoj od dijagonala.

Primijetite da se uzastopni nizovi istih oznaka mogu sjeći (slika 1), ali i preklapati. Ako na primjer postoji niz od pet uzastopnih istih oznaka u istom retku, on donosi tri boda jer se u njemu nalaze tri niza od uzastopne tri oznake (slika 2). Pobjednik je igrač s najviše bodova, a ako više igrača ima najveći broj bodova, svi se oni proglašavaju pobjednicima.

Napiši program koji će za zadano konačno stanje tablice odrediti pobjednike igre te broj bodova koji su pobjednici pojedinačno osvojili.

Ulazni podaci

• U prvom retku nalaze se dva prirodna broja N (1 ≤ N ≤ 7), broj redaka i M (1 ≤ M ≤ 7), broj stupaca tablice na kojoj se igra.
• U drugom retku nalazi se prirodan broj K (1 ≤ K ≤ 10), broj igrača.
• U svakom od sljedećih N redaka nalazi se po M znakova koji prikazuju stanje tablice po završetku igre.
• Svaki znak tablice može biti jedno od sljedećih:
  • veliko slovo engleske abecede (od prvih K slova abecede) ‒ predstavlja polje na kojemu se nalazi odgovarajuća oznaka igrača,
  • znak točke (‘.’) ‒ predstavlja polje koje još nije zauzeto

Izlazni podaci

• U prvom retku treba ispisati oznake pobjednika odvojene razmakom u abecednom poretku.
• U drugom retku treba ispisati broj bodova koji su ostvarili pobjednici, tj. maksimalni broj bodova ostvaren u igri.

Primjeri test podataka

Ulaz

3 3
2
BBB
AA.
BAA

Izlaz

B
1

Ulaz

3 3
1
AAA
AAA
AAA

Izlaz

A
8

Ulaz

4 5
3
CCCCB
CACBB
CAABB
.AAAB

Izlaz

A C
3

Objašnjenje

Igrač A dobio je dva boda za četiri uzastopne oznake u prvom retku i bod za tri uzastopne oznake u prvom stupcu. To su ukupno tri boda. Igrač B dobio je dva boda za četiri oznake u petom stupcu. Igrač C dobio je po bod za tri oznake u drugom stupcu, tri oznake u četvrtom retku i tri oznake na dijagonali koja počinje ćelijom u drugom retku i drugom stupcu te je usmjerena dolje-desno. To su ukupno tri boda. Igrači A i C imaju tri boda što je najveći broj bodova i stoga su pobjednici.