Jump to content
Main menu
Main menu
move to sidebar
hide
Navigation
Main page
Recent changes
Random page
Help about MediaWiki
Bitnami MediaWiki
Search
Search
Create account
Log in
Personal tools
Create account
Log in
Pages for logged out editors
learn more
Contributions
Talk
Editing
1369 - Parcela
Page
Discussion
English
Read
Edit
Edit source
View history
Tools
Tools
move to sidebar
hide
Actions
Read
Edit
Edit source
View history
General
What links here
Related changes
Special pages
Page information
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
==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 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".
Summary:
Please note that all contributions to Bitnami MediaWiki may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see
Bitnami MediaWiki:Copyrights
for details).
Do not submit copyrighted work without permission!
Cancel
Editing help
(opens in new window)
Toggle limited content width