ŠKOLSKO NATJECANJE 2016 / Srednja škola, I. podskupina (1. i 2. razred) - 3. zadatak

Mirko i Slavko na svojim tabletima igraju zaraznu igru Točke. Ploča za igru se sastoji od N * N raznobojnih točaka poredanih u tablicu od redaka i stupaca kao na slici dolje.

U svakom potezu, igrač traži put kroz mrežu. Put počinje na proizvoljnoj točki, kreće se u svakom koraku na susjednu točku dolje, lijevo ili desno (dakle nije dozvoljeno kretanje prema gore). Dodatno, sve točke na putu moraju biti iste boje, te put ne smije kroz istu točku proći više od jednom.

Duljina puta je broj točaka koji put sadrži. Na primjer, put na slici gore je duljine 4.

Zadano je stanje ploče za igru, pronađite duljinu najdužeg mogućeg puta.

ULAZNI PODACI

U prvom redu nalazi se prirodni broj ( ) — veličina ploče za igru. U svakom od sljedećih redova nalazi se niz od točno znakova koji označava jedan redak ploče. Svaki znak je malo slovo engleske abecede koje predstavlja boju odgovarajuće točke.

IZLAZNI PODACI

U prvi red ispišite jedan prirodni broj — traženu duljinu najdužeg mogućeg puta.

BODOVANJE

U test podacima vrijednim 30% bodova ploča je dimenzija 5x5 i sadrži samo boje a i b.

PRIMJERI TEST PODATAKA

ulaz

6
aaaaaa
aaabaa
abbbba
abbbba
aaaaaa
aaabaa

izlaz

18

ulaz

6
aaaaaa
aaabbb
bbbbbb
abbbbb
aaabbb
ccdeaa

izlaz

16