DRŽAVNO NATJECANJE 2015. – Prvi dan natjecanja / Srednja škola, I. podskupina (1. i 2. 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 je matrica od redaka i stupaca koja se sastoji od koncentričnih kvadratnih područja jednakih velikih slova.

Točnije, dvodimenzionalni palindrom se konstruira tako da se krene od jednog slova, oko njega se doda rub kvadrata veličine 3x3 sastavljen od istih velikih slova, oko toga svega se doda rub kvadrata veličine 5x5 sastavljen od istih velikih slova i tako dalje do tražene veličine.

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

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

Ulazni​ podaci

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

U svakom od sljedećih redova nalazi se niz od 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 .

Primjeri test​ podataka

Ulaz

5 2
DDAAA
ADBBA
ABCAA
ABBBA
AAAAA

Izlaz

2

Ulaz

6 3
AAABAA
ABBBCA
ACAAAA
ACABAC
ACAAAC
ACCCCC

Izlaz

5

Ulaz

7 4
AAAAAAA
AAAAAAA
AAAAAAA
MARSRAM
AAAAAAA
AAAAAAA
AAAAAAA

Izlaz

4