4018 - Mos Craciun 3
Enunt
Cunoscutul programator Văndămel are la dispoziție o matrice binară cu n linii (numerotate de la 1 la n) și m coloane (numerotate de la 1 la m). Văndămel poate efectua, de câte ori e posibil, următoarea operație: alege două poziții vecine pe linie sau pe coloană și care conțin ambele valoarea 1 și le transformă în 0. De exemplu, în matricea:
0 1 1 0
1 1 0 0
1 0 0 0
0 1 1 0
el poate alege valorile de 1 de la pozițiile vecine (1,2) și (2,2), le transformă în 0 și obține matricea:
0 0 1 0
1 0 0 0
1 0 0 0
0 1 1 0
Cerința
Văndămel știe să rezolve orice problemă, dar vrea să vadă dacă știți și voi să aflați numărul maxim posibil de operații care se pot efectua pe matricea dată.
Date de intrare
Programul citește de la tastatură numerele n și m și de pe următoarele n linii câte m numere binare reprezentând valorile din matrice.
Date de ieșire
Programul va afișa pe ecran un singur număr natural reprezentând numărul maxim posibil de operații care se pot aplica asupra matricei.
Restricții și precizări
1 ≤ n, m ≤ 100
Exemplul 1:
Intrare
4 4 0 1 1 0 1 1 0 0 1 0 0 0 0 1 1 0
Ieșire
3
Explicație
Se efectuează operațiile la (2,1) și (3,1), la (1,2) și (2,2) și la (4,2) și (4,3). După efectuarea celor 3 operații matricea arată astfel:
0 0 1 0
0 0 0 0
0 0 0 0
0 0 0 0
Exemplul 2:
Intrare
5 4 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1
Ieșire
1