Editing 2779 - Cnt SQ


= 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>