Fişierul intrare/ieşire:	hashtag.in, hashtag.out	Sursă	Algoritmiada 2015 Runda 3
Autor	Mihai Calancea	Adăugată de	Mihai Calancea •klamathix
Timp execuţie pe test	0.5 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Hashtag

Formal, un hashtag de dimensiune N x M este o matrice binară care îndeplineşte următoarele condiţii:

Există indicii (indexaţi de la 0) L1 L2 L3 L4 C1 C2 C3 C4 cu următoarele proprietăţi:

1 ≤ L1 ≤ L2
L2 + 2 ≤ L3 ≤ L4 ≤ N - 2
1 ≤ C1 ≤ C2
C2 + 2 ≤ C3 ≤ C4 ≤ M - 2
Celula (i, j) va fi egală cu caracterul '#' dacă şi numai dacă i este în intervalul [L1, L2] sau în intervalul [L3, L4], iar j este în intervalul [C1, C2] sau în intervalul [C3, C4].

Cu alte cuvinte, un hashtag este compus din două bare verticale şi două bare orizontale care nu au neaparat grosime egală. De-asemenea, din relaţiile de mai sus putem observa că două bare paralele nu se pot atinge, iar cele patru colţuri ale matricei nu pot face parte niciodată din hashtag.

Dându-se o matrice de dimensiuni N x M cu caractere din mulţimea {'.', '#'}, de câte operaţii e nevoie minim pentru a transforma matricea într-un hashtag?

Date de intrare

Fişierul de intrare hashtag.in va conţine pe prima sa linie numerele N şi M. Fiecare din următoarele N linii va conţine un şir de M caractere, fiecare din acestea fiind egal cu '.' sau cu '#'.

Date de ieşire

În fişierul de ieşire hashtag.out se va afla un număr întreg reprezentând numărul minim de celule care trebuie schimbate pentru a obţine un hashtag.

Restricţii

• 5 ≤ N, M ≤ 30

Exemplu

Explicaţie

Pentru hashtagul rezultat indicii vor fi C1 = 2, C2 = 3, C3 = 5, C4 = 5, L1 = 1, L2 = 1, L3 = 3, L4 = 3.

Cum se trimit solutii?