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. Consola va afișa un mesaj de validare a datelor ("Input valid" sau "Input invalid" după caz).

==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
; Consola
: Input valid
==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

if __name__ == "__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("Input invalid")
            return
        else:
            print("Input valid")
        ans = find_largest_square(N, M, A)
        fout.write(str(ans) + "\n")

</syntaxhighlight>

==Explicație cod==
Acest program calculează dimensiunea celui mai mare pătrat format numai din cifra 1 într-o matrice bidimensională dată. 

Funcția `compute_matrices` calculează patru matrici: `LDL`, `CDL`, `LRU`, `CRU`, fiecare fiind de aceeași dimensiune ca matricea de intrare `A`. Matricile `LDL` și `CDL` conțin lungimile celor mai lungi segmente consecutive de cifra 1 din stânga și, respectiv, de sus de fiecare celulă, iar matricile `LRU` și `CRU` conțin lungimile celor mai lungi segmente consecutive de cifra 1 din dreapta și, respectiv, de jos de fiecare celulă. 

În denumirea matricelor din funcția `compute_matrices`, primele trei litere reprezintă inițialele direcțiilor de la care începe numărătoarea segmentelor de cifra 1. Astfel, matricea `LDL` conține lungimile segmentelor consecutive de cifra 1 din stânga fiecărei celule, începând de la stânga și mergând spre dreapta, matricea `CDL` conține lungimile segmentelor consecutive de cifra 1 de sus fiecărei celule, începând de sus și mergând în jos, iar matricea `LRU` conține lungimile segmentelor consecutive de cifra 1 din dreapta fiecărei celule, începând de la dreapta și mergând spre stânga, iar matricea `CRU` conține lungimile segmentelor consecutive de cifra 1 de jos fiecărei celule, începând de jos și mergând în sus.

Funcția `find_largest_square` parcurge fiecare celulă din matricea de intrare și, pentru fiecare celulă, verifică dacă poate fi colțul stânga-sus al unui pătrat și, în caz afirmativ, încearcă să-l mărească progresiv până la limita minimă dintre lungimile segmentelor de cifra 1 din matricile `LDL`, `CDL`, `LRU` și `CRU`. 

Funcția `validate_input` verifică dacă dimensiunile matricei de intrare sunt între 1 și 1000 inclusiv, iar blocul `if __name__ == "__main__":` citește datele de intrare din fișierul "lsq.in", validează dimensiunile matricei de intrare, calculează dimensiunea celui mai mare pătrat de cifra 1 și scrie rezultatul în fișierul "lsq.out".