1576 - zona3

Cerința

Se consideră o matrice cu n linii și m coloane. Spunem că o poziție este liberă dacă elementul de pe linia i și coloana j este egal cu 0 și 1 în caz contrar. Spunem despre mai multe elemente ocupate că formează o zonă, dacă elementele se învecinează pe cele patru direcții (sus, jos, dreapta, stânga).

Calculați pentru fiecare zonă numărul de elemente și afișați noua matrice formată prin înlocuirea elementelor egale cu 1 cu numărul de elemente pe care îl are zona din care face parte elementul respectiv.

Date de intrare

e pe prima linie a fișierului zona3.in se citesc două numere naturale n și m. Următoarele n linii conțin câte m valori 0 sau 1.

Date de ieșire

Scrieți în fișierul zona3.out matricea care rezultă din operațiile specificate în cerință.

Restricții și precizări

• 2 ≤ n, m ≤ 100

Exemplu

Exemplu1

Intrare:

zona3.in

6 8

1 1 0 0 1 1 1 0

0 0 0 1 1 1 0 0

1 1 0 0 0 1 0 0

0 0 0 0 1 1 0 0

1 1 0 1 0 0 0 1

Iesire:

zona3.out

2 2 0 0 7 7 7 0

0 0 0 7 7 7 0 0

8 8 0 0 0 7 0 0

0 8 8 8 8 0 0 0

0 0 0 0 8 8 0 0

2 2 0 1 0 0 0 1

Rezolvare

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

def validare(n, m, matrice):

   # validarea datelor de intrare
   if not (2 <= n <= 100 and 2 <= m <= 100):
       raise ValueError("Dimensiunile matricei trebuie sa fie cuprinse intre 2 si 100")
   if not all(len(linie) == m for linie in matrice):
       raise ValueError("Toate liniile matricei trebuie sa aiba aceeasi lungime")
   for linie in matrice:
       for element in linie:
           if element not in (0, 1):
               raise ValueError("Matricea trebuie sa contina doar elemente 0 sau 1")

def rezolvare(n, m, matrice):

   # implementarea cerintei
   def calculeaza_zona(i, j):
       # calculeaza dimensiunea zonei din care face parte elementul de pe pozitia (i, j)
       if matrice[i][j] != 1:
           return 0
       zona = 0
       stack = [(i, j)]
       while stack:
           x, y = stack.pop()
           if matrice[x][y] == 1:
               zona += 1
               matrice[x][y] = -1
               if x > 0 and matrice[x - 1][y] == 1:
                   stack.append((x - 1, y))
               if x < n - 1 and matrice[x + 1][y] == 1:
                   stack.append((x + 1, y))
               if y > 0 and matrice[x][y - 1] == 1:
                   stack.append((x, y - 1))
               if y < m - 1 and matrice[x][y + 1] == 1:
                   stack.append((x, y + 1))
       return zona

   # calculeaza dimensiunea fiecarei zone si inlocuieste valorile cu numarul de elemente din zona
   for i in range(n):
       for j in range(m):
           if matrice[i][j] == 1:
               zona = calculeaza_zona(i, j)
               for x in range(n):
                   for y in range(m):
                       if matrice[x][y] == -1:
                           matrice[x][y] = zona
               matrice[i][j] = zona

   return matrice

def main():

   # citim datele de intrare
   with open("zona3.in", "r") as f:
       n, m = map(int, f.readline().split())
       matrice = [list(map(int, f.readline().split())) for _ in range(n)]

   # validam datele de intrare
   validare(n, m, matrice)

   # rezolvam problema
   rezultat = rezolvare(n, m, matrice)

   # afisam rezultatul in fisierul de iesire
   with open("zona3.out", "w") as f:
       for linie in rezultat:
           f.write(" ".join(str(x) for x in linie))
           f.write("\n")

if __name__ == '__main__':

   main()

</syntaxhighlight>

Explicații

Codul citeste datele din fisierul "zona3.in", care contine o matrice de 0 si 1 de dimensiune n x m. Scopul este de a gasi toate zonele formate din 1 si de a inlocui fiecare element 1 cu numarul de elemente din zona din care face parte.

1. 1 In functia validare se verifica daca datele de intrare sunt in limitele impuse de cerinta: n si m sunt intre 2 si 100. Daca aceasta conditie nu este indeplinita, functia arunca o exceptie cu mesajul corespunzator.

1. 2 Functia rezolvare are doua obiective principale: sa gaseasca zonele formate din 1 si sa inlocuiasca fiecare element 1 cu numarul de elemente din zona din care face parte. Acest lucru se realizeaza prin parcurgerea matricei si identificarea tuturor elementelor care sunt egale cu 1. Dupa aceea, se calculeaza numarul de elemente din zona din care face parte fiecare element 1 si se inlocuieste valoarea cu aceasta. Pentru a gasi numarul de elemente dintr-o zona, se foloseste o functie auxiliara gaseste_zona, care cauta toate elementele vecine ale unui element 1 si le adauga intr-o zona. Procesul continua pana cand nu mai exista niciun element vecin de adaugat.

1. 3 Functia main citeste datele de intrare, verifica daca sunt valide, aplica functia rezolvare si afiseaza matricea rezultata in fisierul "zona3.out".