1369 - Parcela

Cerința

Cerința Se dau n și m reprezentând dimensiunile unui tablou bidimensional format din elementele 0 si 1. Se definește o parcelă ca fiind o grupare de elemente vecine cu valoarea 1, condiția de vecinătate dintre două elemente fiind ca, luat unul dintre ele ca referință, celălalt să fie deasupra, dedesupt, în stânga sau în dreapta acestuia. Parcele se numerotează parcurgând matricea de sus în jos și de la stânga la dreapta, astfel:

primul element din matrice egal cu 1 face parte din parcela numărul 1 primul element din matrice care este egal cu 1 și nu face face parte din parcela 1 face parte din parcela 2; primul element din matrice care este egal cu 1 și nu face face parte din parcelele 1 și 2 face parte din parcela 3; etc. Să se determine numărul de parcele nr, aria maximă a unei parcele amax și respectiv numărul parcelei cu arie maximă pmax.

Date de intrare

Fișierul de intrare parcela.in conține pe prima linie numerele n și m, iar pe a doua linie un tablou bidimensional cu n×m elemente.

Date de ieșire

Fișierul de ieșire parcela.out va conține pe prima linie numerele nr amax pmax cu semnificațiile din enunț, separate prin câte un spațiu.

Restricții și precizări

• 1 ≤ n,m ≤ 100

Exemplu

Exemplu1

Intrare:

parcela.in

5 6

0 1 1 1 0 1

0 0 1 0 0 1

0 1 0 0 0 1

0 0 0 0 1 1

1 1 1 0 0 1

Iesire:

parcela.out

4 6 2

Rezolvare

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

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

   if n < 1 or m < 1 or n > 100 or m > 100:
       return False
   if len(matrice) != n:
       return False
   for linie in matrice:
       if len(linie) != m:
           return False
       for element in linie:
           if element != 0 and element != 1:
               return False
   return True

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

   nr_parcele = 0
   max_aria = 0
   parcela_max_aria = 0
   parcurs = [[False for _ in range(m)] for _ in range(n)]

   def parcurgere(linie: int, coloana: int, numar_parcela: int):
       if linie < 0 or coloana < 0 or linie >= n or coloana >= m:
           return
       if matrice[linie][coloana] == 0 or parcurs[linie][coloana]:
           return
       nonlocal nr_parcele
       nonlocal max_aria
       nonlocal parcela_max_aria
       nr_parcele += 1
       aria = 0
       coada = [(linie, coloana)]
       while coada:
           x, y = coada.pop(0)
           if x < 0 or y < 0 or x >= n or y >= m:
               continue
           if matrice[x][y] == 0 or parcurs[x][y]:
               continue
           parcurs[x][y] = True
           aria += 1
           if aria > max_aria:
               max_aria = aria
               parcela_max_aria = numar_parcela
           coada.append((x - 1, y))
           coada.append((x + 1, y))
           coada.append((x, y - 1))
           coada.append((x, y + 1))

   for i in range(n):
       for j in range(m):
           if matrice[i][j] == 1 and not parcurs[i][j]:
               parcurgere(i, j, nr_parcele + 1)

   return nr_parcele, max_aria, parcela_max_aria

if __name__ == '__main__':

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

   if not validare(n, m, matrice):
       with open('parcela.out', 'w') as f:
           f.write("Date de intrare invalide.")
   else:
       nr_parcele, max_aria, parcela_max_aria = rezolvare(n, m, matrice)
       with open('parcela.out', 'w') as f:
           f.write(f"{nr_parcele} {max_aria} {parcela_max_aria}")

</syntaxhighlight>

Explicații

Acest cod rezolvă problema numită "Parcela", în care trebuie să determinăm numărul de parcele de teren și aria maxima a unei parcele dintr-o matrice 2D cu valori de 0 și 1. Mai precis, programul citeste datele de intrare din fișierul "parcela.in", validează datele, determină numărul de parcele, aria maximă și numărul parcelei cu aria maximă, și afișează aceste valori în fișierul "parcela.out".

1. 1 Funcția validare primește 3 argumente: n - numărul de linii al matricei, m - numărul de coloane al matricei, și matrice - matricea propriu-zisă. Această funcție validează datele de intrare, verificând dacă dimensiunile matricei sunt valide și dacă toate valorile matricei sunt 0 sau 1.

1. 2 Funcția rezolvare primește aceeași 3 argumente ca și funcția validare, și calculează numărul de parcele, aria maximă și numărul parcelei cu aria maximă. Pentru a face acest lucru, funcția folosește o metodă de parcurgere a matricei, care verifică fiecare celulă din matrice și verifică dacă aceasta face parte dintr-o parcelă sau nu. Pentru fiecare parcelă găsită, funcția calculează aria acesteia, și ține evidența parcelei cu aria maximă.

1. 3 În funcția main, programul citeste datele de intrare din fișierul "parcela.in", validează datele folosind funcția validare, și, dacă datele sunt valide, calculează valorile dorite folosind funcția rezolvare. Dupa ce valorile sunt calculate, acestea sunt afișate în fișierul "parcela.out".