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 ⩽ N, M ⩽ 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
0 1 1 1 1 0 0
0 1 0 1 1 1 1
0 1 0 0 1 0 1
0 1 1 1 1 1 1
0 0 0 0 0 1 1
0 0 0 0 0 1 1

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

if __name__ == "__main__":

   main()

</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 funcția `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".