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

Valid input

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("Invalid input!")
           return
       else:
           print("Valid input")
       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".