Editing 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===
 
parcela.in
<syntaxhighlight lang="python">
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
</syntaxhighlight>

parcela.out
<syntaxhighlight lang="python">
4 6 2
</syntaxhighlight>


==Rezolvare==
 <syntaxhighlight lang="python">
 
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".

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.

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

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