Danciu: Pagină nouă: = 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`...

2024-06-04T07:35:39Z

Pagină nouă: = Cerința = Se dă o matrice binară (valori <code>0</code> și <code>1</code>). Să se determine câte pătrate există cu proprietatea că acestea au pe marginea lor doar valori <code>1</code>. = Date de intrare = Fișierul de intrare <code>cntsq.in</code> conține pe prima linie numerele <code>N</code> și <code>M</code>, reprezentând numărul de linii și numărul de coloane ale matricei, apoi <code>N</code> linii, pe fiecare câte <code>M</code> valori <code>0</code>...

New page

= Cerința =
Se dă o matrice binară (valori <code>0</code> și <code>1</code>). Să se determine câte pătrate există cu proprietatea că acestea au pe marginea lor doar valori <code>1</code>.

= Date de intrare =
Fișierul de intrare <code>cntsq.in</code> conține pe prima linie numerele <code>N</code> și <code>M</code>, reprezentând numărul de linii și numărul de coloane ale matricei, apoi <code>N</code> linii, pe fiecare câte <code>M</code> valori <code>0</code> sau <code>1</code>, neseparate prin niciun spațiu, reprezentând elementele matricei.

= Date de ieșire =
Fișierul de ieșire <code>cntsq.out</code> va conține pe prima linie numărul <code>C</code>, reprezentând numărul de pătrate ce conțin doar <code>1</code> pe marginea lor.

= Restricții și precizări =

* <code>1 ≤ N, M ≤ 1000</code>
* Se consideră pătrat și cel de latură <code>1</code> (conține doar un element).
* Fie un pătrat determinat de <code>(i1, j1)</code> colțul stânga sus, <code>(i2, j2)</code> colțul dreapta jos. Se definește marginea pătratului ca fiind mulțimea de puncte <code>(x, y)</code> care respectă cel puțin una din condițiile: <code>((x = i1 sau x = i2) și (j1 ≤ y ≤ j2))</code> sau <code>((y = j1 sau y = j2) și (i1 ≤ x ≤ i2))</code>.

= Exemplu: =
<code>cntsq.in</code>
3 3
111
101
111
<code>cntsq.out</code>
9
<code>cntsq.in</code>
7 7
0000000
0111100
0101111
0100101
0111111
0000011
0000011
<code>cntsq.out</code>
27

== Rezolvare ==
<syntaxhighlight lang="python3">
def count_squares(matrix):
n, m = len(matrix), len(matrix[0])
dp = [[0] * (m + 1) for _ in range(n + 1)]
count = 0

for i in range(1, n + 1):
for j in range(1, m + 1):
if matrix[i - 1][j - 1] == 1:
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
size = dp[i][j]
while size > 0:
count += 1
size -= 1

return count

def main():
with open("cntsq.in", "r") as fin, open("cntsq.out", "w") as fout:
n, m = map(int, fin.readline().split())
matrix = []
for _ in range(n):
row = list(map(int, fin.readline().strip()))
matrix.append(row)

result = count_squares(matrix)
fout.write(str(result) + "\n")

if __name__ == "__main__":
main()
</syntaxhighlight>

2779 - Cnt SQ - Revision history