3220 - foto

Enunț

Alina este pasionată de fotografiile alb-negru. Ea ales o imagine pe care a codificat-o binar într-o matrice de dimensiune n x m cu valori 0 corespunzătoare pentru alb (pe care le-a numit puncte luminoase) și cu valori 1 corespunzătoare pentru negru (pe care le-a numit puncte întunecate). Astfel, ea identifică în imaginea codificată zone luminoase și zone întunecate, o zonă fiind o porțiune a matricei care conține elemente cu aceeași valoare, trecerea de la un element la altul al zonei făcându-se doar prin deplasări pe orizontală sau pe verticală.

Cerința

Ajutați-o pe Alina să găsească cea mai luminoasă zonă și determinați numărul de puncte luminoase ale acesteia.

Date de intrare

Pe prima linie a fișierului text foto.in se găsesc două numere naturale n și m care reprezintă numărul liniilor, respectiv numărul coloanelor matricei. Pe următoarele n linii se găsesc câte m valori binare, separate prin câte un spațiu, reprezentând elementele matricei care codifică imaginea.

Date de ieșire

Fișierul de ieșire foto.out trebuie să conțină o singură linie pe care se va afla numărul punctelor din cea mai luminoasă zonă a imaginii.

Restricții și precizări

• 1 ≤ n ≤ 100, 1 ≤ m ≤ 100, numere naturale
• dacă nu există nicio zonă luminoasă, se va considera că cea mai luminoasă zonă are 0 elemente

Exemplu

Exemplu1

foto.in

6 6

1 0 0 1 1 1

1 1 0 1 0 1

1 0 0 1 0 0

1 1 1 0 1 1

1 0 0 1 1 0

1 0 0 1 1 1

foto.out

5

Rezolvare

<syntaxhighlight lang="python" line="1">

def validare(n: int, m: int, matrice: list) -> bool:

   if not (1 <= n <= 100 and 1 <= m <= 100):
       return False
   if len(matrice) != n or any(len(row) != m for row in matrice):
       return False
   if not all(0 <= val <= 1 for row in matrice for val in row):
       return False
   return True

def rezolvare(n: int, m: int, matrice: list) -> int:

   def dfs(x, y):
       nonlocal visited, puncte_luminoase, dx, dy
       visited[x][y] = True
       puncte_luminoase += 1
       for i in range(4):
           nx, ny = x + dx[i], y + dy[i]
           if 0 <= nx < n and 0 <= ny < m and matrice[nx][ny] == 0 and not visited[nx][ny]:
               dfs(nx, ny)

   dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
   visited = [[False] * m for _ in range(n)]
   rezultat = 0
   for i in range(n):
       for j in range(m):
           if matrice[i][j] == 0 and not visited[i][j]:
               puncte_luminoase = 0
               dfs(i, j)
               rezultat = max(rezultat, puncte_luminoase)
   return rezultat

if __name__ == "__main__":

   with open("foto.in", "r") as fin:
       n, m = map(int, fin.readline().split())
       matrice = [list(map(int, fin.readline().split())) for _ in range(n)]

   if validare(n, m, matrice):
       with open("foto.out", "w") as fout:
           fout.write(str(rezolvare(n, m, matrice)))
   else:
       print("Date de intrare invalide.")

</syntaxhighlight>

Explicații

Codul implementează o soluție pentru problema Magic1, care cere calcularea numărului minim de tratate necesare pentru a aplica o serie de rețete pe un creuzet cu o anumită capacitate și cu anumite caracteristici de aplicare a rețetelor. Conform enunțului problemei, fiecare rețetă este aplicată în două etape și produce un anumit număr de picături, iar un tratament conține un anumit număr de rețete și se consumă P pagini. Problema cere determinarea numărului minim de tratate necesare pentru a aplica toate rețetele pe creuzet, ținând cont de caracteristicile acestora.

Funcția validare verifică dacă valorile de intrare respectă cerințele problemei (adică dacă C, N și P sunt în intervalul [1, 10^7], iar N și P sunt în intervalul [2, 10^7]) și returnează True dacă valorile sunt valide și False în caz contrar.

Funcția rezolvare primește ca argumente lista de rețete și valorile C, N și P și calculează numărul minim de tratate necesare pentru a aplica toate rețetele. Pentru fiecare rețetă, numărul de picături este adăugat la numărul total de picături, iar dacă acesta depășește capacitatea creuzetului, numărul de tratamente necesare este incrementat și totalul picăturilor este resetat. Dacă la final numărul de picături rămase în creuzet este nenul, un tratament suplimentar este necesar. Rezultatul final este calculat prin împărțirea numărului de tratamente la numărul total de rețete care se pot include într-un tratament (adică N * P) și adăugarea unui tratament suplimentar dacă numărul de tratamente este divizibil cu N * P.

Funcția main citeste datele de intrare din fișierul "magic1.in", verifică dacă acestea sunt valide folosind funcția validare, apoi calculează și afișează în fișierul "magic1.out" rezultatul obținut prin apelul funcției rezolvare.În primul rând, am observat că ai definit o funcție validare care primește ca parametru numele fișierului de intrare nume_fisier și care verifică dacă datele de intrare sunt corecte. În cadrul acestei funcții, ai deschis fișierul de intrare și ai citit primele două numere care reprezintă numărul de linii și coloane ale matricei. Apoi, am parcurs fiecare linie și am verificat dacă aceasta are aceeași lungime cu numărul de coloane specificat în fișierul de intrare și dacă conține doar 0-uri și 1-uri. În caz contrar, am returnat False semnalizând astfel că datele de intrare nu sunt corecte.

În cazul în care datele de intrare sunt corecte, am definit funcția rezolvare care primește ca parametri numele fișierului de intrare nume_fisier, numărul de linii n și numărul de coloane m. În cadrul acestei funcții, am deschis fișierul de intrare și am citit matricea de elemente binare. Pentru a determina cea mai luminoasă zonă, am parcurs fiecare element al matricei și am folosit o funcție recursivă dfs pentru a explora toate elementele adiacente cu aceeași valoare ca elementul curent. Pe măsură ce am parcurs matricea, am menținut o variabilă max_zona care reprezintă dimensiunea celei mai mari zone luminoase întâlnite până în acel moment.

În cadrul funcției dfs, am verificat dacă elementul curent este valid (nu a fost deja vizitat și are aceeași valoare ca elementul inițial). Dacă este valid, am marcat elementul curent ca vizitat și am explorat recursiv toate elementele adiacente cu aceeași valoare. În timp ce am explorat aceste elemente, am actualizat dimensiunea zonei curente curent_zona și am verificat dacă aceasta este mai mare decât dimensiunea maximă a zonei luminoase întâlnită până în acel moment. Dacă este cazul, ai actualizat max_zona.

La final, am scris dimensiunea maximă a zonei luminoase în fișierul de ieșire.

În cadrul funcției main, am citit numele fișierului de intrare și am apelat funcția validare pentru a verifica dacă datele de intrare sunt corecte. Dacă sunt corecte, apeleaza funcția rezolvare pentru a determina dimensiunea celei mai mari zone luminoase și am scris rezultatul în fișierul de ieșire. În caz contrar, afișaza un mesaj de eroare