Županijsko natjecanje / Osnovna škola (7. razred) 2022 - 2. zadatak

Potišten jer nije uspio ispraviti grešku u izrazu iz prošlog zadatka, Mirko je uzeo svoju najdražu kvadratnu tablicu koja se sastoji od N redaka i N stupaca te je po njoj počeo postavljati žetone. Svako polje tablice je ili ostavio prazno ili je na njega stavio žeton.

Taman kada se počeo bolje osjećati došao je Slavko i zarotirao njegovu tablicu. Uzrujan, Mirko je odlučio da neće više dopustiti Slavku ovakve provokacije. Zato će na neka preostala prazna polja staviti nove žetone, ali tako da na kraju tablica ima žetone na istim poljima neovisno o rotaciji. Preciznije, ako tablica prije rotacije ima žeton na polju u i-tom retku i j-tom stupcu, onda nakon rotacije za bilo koji višekratnik od 90° mora također imati žeton u i-tom retku i j-tom stupcu, a isto vrijedi i za prazna polja bez žetona.

Slika prikazuje tri rotacije tablice za 90° u smjeru kazaljke na satu:

Ova tablica očito ne zadovoljava Mirkov uvjet. Promotrimo li polje u prvom retku i drugom stupcu vidjet ćemo da se tamo na početku nalazi žeton, ali nakon rotacije za 270° na polju u prvom retku i drugom stupcu nema žetona.

Samo je pitanje vremena kada će Slavko opet zarotirati njegovu tablicu. Mirko stoga želi što prije postaviti žetone na traženi način. Zato te moli da mu odgovoriš koliko najmanje žetona treba postaviti kako bi tablica zadovoljavala navedeni uvjet.

Ulazni podaci

U prvom je retku prirodan broj N (1 ≤ N ≤ 500), broj iz teksta zadatka.

U svakom od sljedećih N redaka je po N znakova ‘.’ i ‘O’ koji predstavljaju tablicu. Ako je znak u i-tom retku i j-tom stupcu tablice ‘.’ onda je to polje prazno, a inače se na polju nalazi žeton.

Izlazni podaci

U prvi redak ispiši najmanji broj dodatnih žetona koje treba postaviti kako bi tablica zadovoljavala uvjet iz teksta zadatka.

Probni primjeri

Ulaz

3
.O.
O..
.O.

Izlaz

1

Opis prvog probnog primjera:

Stavimo li žeton na polje u drugom retku i trećem stupcu, dobit ćemo tablicu koja izgleda isto kako god ju zarotirali.

Ulaz

3
...
.O.
...

Izlaz

0

Opis drugog probnog primjera:

Ova tablica već zadovoljava uvjet iz zadatka pa ne treba postavljati dodatne žetone.

Ulaz

4
O...
..O.
.O..
...O

Izlaz

4