Editing 2724 - LSQ

==Cerința==
Se dă o matrice binară (valori 0 și 1). Să se determine care este latura maximă a unui pătrat cu proprietatea că acesta are pe marginea sa doar valori 1.

==Date de intrare==
Fișierul de intrare lsq.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 lsq.out va conține pe prima linie numărul L, reprezentând lungimea maximă a laturii unui pătrat ce conține doar 1 pe marginea sa.

==Restricții și precizări==
* 1 &les; N, M &les; 1000
* Se consideră pătrat și cel de latură 1 (conține doar un element).
==Exemplu==
lsq.in

 7 7
 0000000
 0111100
 0101111
 0100101
 0111111
 0000011
 0000011
lsq.out

 4
==Explicație==

0 0 0 0 0 0 0<br>
0 <b>1 1 1 1</b> 0 0<br>
0 <b>1</b> 0 1 <b>1</b> 1 1<br>
0 <b>1</b> 0 0 <b>1</b> 0 1<br>
0 <b>1 1 1 1</b> 1 1<br>
0 0 0 0 0 1 1<br>
0 0 0 0 0 1 1<br>

==Rezolvare==
<syntaxhighlight lang="python">
Nmax = 1005


def compute_matrices(N, M, A):
    LDL = [[0] * M for _ in range(N)]
    CDL = [[0] * M for _ in range(N)]
    LRU = [[0] * M for _ in range(N)]
    CRU = [[0] * M for _ in range(N)]

    for i in range(N):
        for j in range(M):
            if A[i][j] == 1:
                LDL[i][j] = 1 + LDL[i][j - 1] if j > 0 else 1
                CDL[i][j] = 1 + CDL[i - 1][j] if i > 0 else 1

    for i in range(N - 1, -1, -1):
        for j in range(M - 1, -1, -1):
            if A[i][j] == 1:
                LRU[i][j] = 1 + LRU[i][j + 1] if j < M - 1 else 1
                CRU[i][j] = 1 + CRU[i + 1][j] if i < N - 1 else 1

    return LDL, CDL, LRU, CRU


def find_largest_square(N, M, A):
    LDL, CDL, LRU, CRU = compute_matrices(N, M, A)
    ans = 0
    for i in range(N):
        for j in range(M):
            for L in range(min(LDL[i][j], CDL[i][j]), ans, -1):
                if L <= min(LRU[i - L + 1][j - L + 1], CRU[i - L + 1][j - L + 1]):
                    ans = L
                    break
    return ans

def validate_input(n: int, m: int) -> bool:
    return 1 <= n <= 1000 and 1 <= m <= 1000

def main():
    with open("lsq.in", "r") as fin, open("lsq.out", "w") as fout:
        N, M = map(int, fin.readline().split())
        A = [list(map(int, fin.readline().strip())) for _ in range(N)]
        if not validate_input(N, M):
            print("Invalid input!")
            return
        ans = find_largest_square(N, M, A)
        fout.write(str(ans) + "\n")


if __name__ == "__main__":
    main()

</syntaxhighlight>

==Explicație cod==
Acesta este un program Python care calculează dimensiunea celui mai mare pătrat complet format din cifrele de 1 dintr-o matrice dată. Matricea este dată ca o listă de liste de cifre. Algoritmul folosit pentru a găsi răspunsul constă în calcularea a patru matrice auxiliare, folosind programarea dinamică pentru a calcula lungimea celui mai mare pătrat posibil cu colțul din stânga sus la poziția curentă. Apoi, se parcurge matricea și se caută cel mai mare pătrat complet, verificând dacă toate cele patru laturi au o lungime cel puțin egală cu dimensiunea pătratului. În caz afirmativ, se actualizează dimensiunea maximă a pătratului.

Funcția validate_input() verifică dacă intrarea este validă, adică dacă dimensiunea matricei se află între 1 și 1000 inclusiv. Funcția main() citește matricea din fișierul "lsq.in", validează intrarea și apoi calculează și scrie dimensiunea celui mai mare pătrat complet în fișierul "lsq.out".