DRŽAVNO NATJECANJE 2015. – Prvi dan natjecanja / Srednja škola, II. podskupina (3. i 4. razred) - 1. zadatak

Mirko i Slavko se obožavaju igrati palindromima – nizovima znakova koji se čitaju jednako sprijeda i straga.

Kada im je dosadila jednodimenzionalnost običnih palindroma, definirali su na sljedeći način dvodimenzionalne palindrome:

Dvodimenzionalni palindrom veličine K je matrica od K redaka i K stupaca takva da su svaki redak i svaki stupac palindromi.

Dakle, ako odaberemo bilo koji redak (odnosno stupac) onda je riječ koju dobijemo tako da napišemo sva slova iz tog retka (odnosno stupca) s lijeva na desno (odnosno odozgo prema dolje) palindrom.

Zadano je kvadratno polje koje se sastoji od velikih slova organiziranih u N redaka i N stupaca.

Napišite program koji će za zadani broj K odrediti koliko je najmanje znakova potrebno promijeniti kako bi polje sadržavalo neki dvodimenzionalni palindrom veličine K.

Ulazni​ podaci

U prvom redu nalaze se dva prirodna broja N i K (N ≤ 100, K ≤ N) - redom dimenzije zadanog kvadratnog polja te veličina traženog palindroma.

U svakom od sljedećih N redova nalazi se niz od N velikih slova engleske abecede – jedan redak polja.

Izlazni podaci

U prvi i jedini red ispišite traženi najmanji broj znakova koje je potrebno promijeniti da bi kvadratno polje sadržavalo dvodimenzionalni palindrom veličine K.

Primjeri test​ podataka

Ulaz

5 2
HRINF
HRKUP
IKUPP
NINFO
FOFNI

Izlaz

1

Ulaz

5 3
DDAAA
ADBBA
ABCAA
ABBBA
AAAAA

Izlaz

2

Ulaz

6 4
CBCBCC
BBBBBB
ABBCAC
BEECAB
CCECAC
ABBBCC

Izlaz

4