Popa Bogdan Ioan (PopaBogdan) Cerința
Se dă o matrice binară (valori 0 și 1). Să se determine câte pătrate există cu proprietatea că acestea au pe marginea lor doar valori 1.
Date de intrare
Fișierul de intrare cntsq.in conține pe prima linie numerele N și M, reprezentând numărul de linii și numărul de coloane ale matricei, apoi N linii, pe fiecare câte M valori 0 sau 1, neseparate prin niciun spațiu, reprezentând elementele matricei.
Date de ieșire
Fișierul de ieșire cntsq.out va conține pe prima linie numărul C, reprezentând numărul de pătrate ce conțin doar 1 pe marginea lor.
Restricții și precizări
1 ≤ N, M ≤ 1000- Se consideră pătrat și cel de latură
1(conține doar un element). - Fie un pătrat determinat de
(i1, j1)colțul stânga sus,(i2, j2)colțul dreapta jos. Se definește marginea pătratului ca fiind mulțimea de puncte(x, y)care respectă cel puțin una din condițiile:((x = i1 sau x = i2) și (j1 ≤ y ≤ j2))sau((y = j1 sau y = j2) și (i1 ≤ x ≤ i2)).
Exemplu:
cntsq.in
3 3 111 101 111
cntsq.out
9
cntsq.in
7 7 0000000 0111100 0101111 0100101 0111111 0000011 0000011
cntsq.out
27