Državno natjecanje iz informatike 2017. / Srednja škola / Prva podskupina (1. i 2. razred) / prvi dan - 2. zadatak

Mirko razvija umjetnu inteligenciju za popularnu stratešku igru Mlin. Ploča za igru se sastoji od 24 polja u pravokutnoj mreži. Svako polje je označeno s dva znaka — oznakom retka i stupca. Retci su označeni malim slovima engleske abecede od “a” do “g” odozgo prema dolje, a stupci znamenkama od “1” do “7” slijeva nadesno. Neki parovi polja su povezani horizontalnim ili vertikalnim segmentima kao na slici dolje.

Pozicija je ploča za igru na kojoj svako polje sadrži najviše jednu figuru crne ili bijele boje. Mlin je niz od tri figure iste boje koje leže poredane u istom smjeru (horizontalno ili vertikalno) na uzastopnim poljima povezanim segmentima. Primjerice, pozicija na slici sadrži točno dva mlina: bijele figure na poljima g1, g4 i g7 čine jedan dok crne figure na poljima b2, d2 i f2 čine drugi. Poziciju možemo prikazati pomoću tablice znakova. Tablica se sastoji od 7 redaka i 7 stupaca koji odgovaraju retcima i stupcima ploče za mlin. Znak na pojedinoj poziciji u tablici se određuje na sljedeći način:

• Horizontalni mlin je označeni nizom znakova “-” (minus), od prvog do trećeg polja u mlinu uključujući i sve pozicije u tablici između tih polja.
• Vertikalni mlin je označeni nizom znakova “|” (vertikalna crta, ASCII 124), od prvog do trećeg polja u mlinu uključujući i sve pozicije u tablici između tih polja.
• Ukoliko polje sudjeluje i u vertikalnom i u horizontalnom mlinu označeno je s znakom “+” (plus).
• Polja na kojima su bijele figure, a ne sudjeluju u mlinu su označena malim slovom “o”.
• Polja na kojima su crne figure, a ne sudjeluju u mlinu su označena malim slovom “x”.
• Polja na kojima nema figura označena su znakom “*” (zvjezdica).
• Svi ostali znakovi su “.” (točka).

Zadane su lokacije i boja figura na ploči. Odredite tablicu znakova koja prikazuje zadanu poziciju.

Ulazni podaci

U prvom redu nalazi se cijeli broj n (0 ≤ n ≤ 24) — broj figura na ploči u zadanoj poziciji. U j-tom od sljedećih n redova nalazi se niz znakova fj i znak cj odvojeni jednim razmakom.

Niz znakova fj je oznaka polja koje sadrži j-tu figuru te se sastoji od malog slova engleske abecede i znamenke. Znak c je ili “c” ili “b” te označava boju j-te figure — redom crnu ili bijelu. Svaka od oznaka je jedna od 24 ispravne oznaka polja sa slike gore, a niti jedne dvije figure se ne nalaze na istom polju.

Izlazni podaci

Ispišite 7 redova od kojih svaki sadrži niz od 7 znakova — prikaz zadane pozicije.

Bodovanje

• U test podacima vrijednim 20% bodova ne pojavljuje se niti jedan mlin.
• U dodatnim test podacima vrijednim 20% bodova jedini mlinovi koji se pojavljuju su horizontalni.
• U dodatnim test podacima vrijednim 20% bodova svako polje sudjeluje u najviše jednom mlinu.

Primjeri test podataka

Ulaz

11
b2 c
d2 c
f2 c
d5 c
g1 b
g4 b
g7 b
d3 c
b6 b
d6 c
f6 b

Izlaz

*..*..*
.|.*.o.
.|***..
*|x.xx*
.|***..
.|.*.o.
-------

Ulaz

9
d3 c
d2 b
d1 c
b2 b
b4 c
b6 b
a1 b
g7 c
d7 c

Izlaz

o..*..*
.o.x.o.
..***..
xox.**x
..***..
.*.*.*.
*..*..x

Ulaz

13
f2 c
e4 c
f4 c
f6 c
g4 c
b6 b
a7 b
g7 b
d7 b
a1 b
a4 b
b4 c
b2 c

Izlaz

------+
.x.x.o|
..***.|
***.**|
..*|*.|
.--+--|
*..|..|