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
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}")
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 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.
- 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ă.
- 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".
