2724 - LSQ: Difference between revisions

From Bitnami MediaWiki
Cata (talk | contribs)
No edit summary
Cata (talk | contribs)
No edit summary
Line 6: Line 6:


==Date de ieșire==
==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.
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==
==Restricții și precizări==
Line 26: Line 26:
: 4
: 4
; Consola
; Consola
: Valid input
: Input valid
==Explicație==
==Explicație==


Line 82: Line 82:
         A = [list(map(int, fin.readline().strip())) for _ in range(N)]
         A = [list(map(int, fin.readline().strip())) for _ in range(N)]
         if not validate_input(N, M):
         if not validate_input(N, M):
             print("Invalid input!")
             print("Input invalid")
             return
             return
         else:
         else:
             print("Valid input")
             print("Input valid")
         ans = find_largest_square(N, M, A)
         ans = find_largest_square(N, M, A)
         fout.write(str(ans) + "\n")
         fout.write(str(ans) + "\n")
Line 96: Line 96:


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


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".
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".

Revision as of 07:01, 3 May 2023

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".