1507 - grupuri

Cerința

Scrieţi un program care citeşte din fişierul de intrare un număr natural n şi o matrice pătratică A de dimensiune n x n, elementele acesteia putând avea doar valorile 0 sau 1. Două elemente A[i1][j1] şi A[i2][j2] sunt adiacente dacă sunt “vecine” pe o aceeaşi linie sau coloană: (i1 = i2 şi |j1-j2|=1) sau (j1=j2 şi |i1-i2|=1). Un grup reprezintă fie un singur element al matricii având valoarea 1, neadiacent cu niciun alt element cu valoarea 1, fie o mulţime de elemente având valoarea 1, fiecare dintre ele fiind adiacent cu cel puţin un alt element din mulţimea respectivă şi neadiacent cu niciun alt element din alt grup. Programul afişează în fişierul de ieşire numărul de grupuri conţinute de matrice.

Date de intrare

Fișierul de intrare grupuri.in conține pe prima linie numărul n, iar pe următoarele n linii câte n numere naturale 0 sau 1, reprezentând elementele matricei A.

Date de ieșire

Fișierul de ieșire grupuri.out va conține pe prima linie numărul de grupuri prezente în matricea din fişierul de intrare.

Restricții și precizări

• 2 ≤ n ≤ 100

Exemplu

Exemplu1

Intrare:

grupuri.in

4

1 0 0 1

0 0 1 1

0 1 0 1

1 1 0 0

Iesire:

grupuri.out

3

Rezolvare

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

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

   # Verificăm dacă matricea are dimensiunea n x n
   if len(a) != n:
       return False
   for i in range(n):
       # Verificăm dacă fiecare linie are dimensiunea n și dacă fiecare element are valoarea 0 sau 1
       if len(a[i]) != n or any(val != 0 and val != 1 for val in a[i]):
           return False
   return True

def dfs(a: list[list[int]], i: int, j: int, visited: set[tuple[int, int]]) -> None:

   # Adăugăm elementul (i, j) la grup și îl marcam ca vizitat
   visited.add((i, j))
   # Căutăm toate elementele cu valoarea 1 adiacente cu elementul (i, j) și le adăugăm la grup
   for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
       ni, nj = i + di, j + dj
       if 0 <= ni < len(a) and 0 <= nj < len(a) and a[ni][nj] == 1 and (ni, nj) not in visited:
           dfs(a, ni, nj, visited)

def rezolvare(n: int, a: list[list[int]]) -> int:

   groups = 0
   visited = set()
   for i in range(n):
       for j in range(n):
           if a[i][j] == 1 and (i, j) not in visited:
               # Am găsit un nou grup de elemente cu valoarea 1
               dfs(a, i, j, visited)
               groups += 1
   return groups

def main() -> None:

   with open("grupuri.in", "r") as fin, open("grupuri.out", "w") as fout:
       n = int(fin.readline())
       a = [list(map(int, fin.readline().split())) for _ in range(n)]
       if not validare(n, a):
           fout.write("Matricea de intrare nu este valida\n")
           return
       fout.write(str(rezolvare(n, a)) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>

Explicații

1. 1 Funcția validare verifică dacă matricea dată este validă, adică dacă are dimensiunea n x n și dacă toate elementele sale sunt 0 sau 1. Funcția returnează True dacă matricea este validă și False în caz contrar.

1. 2 Funcția dfs implementează o căutare în adâncime (DFS) pentru a identifica toate elementele din același grup cu elementul (i, j). Funcția primește matricea dată a, poziția inițială a elementului (i, j), și un set de tupluri visited care conține toate pozițiile marcate ca vizitate în timpul căutării. Funcția parcurge toate elementele adiacente cu (i, j) care au valoarea 1 și le adaugă la grup și le marchează ca vizitate, apoi apelează recursiv dfs pe fiecare element adiacent, pentru a adăuga toate elementele din același grup.

Funcția principală rezolvare implementează algoritmul de rezolvare a problemei, care primește matricea dată și returnează numărul de grupuri de elemente cu valoarea 1 din matrice. Algoritmul utilizează o metodă greedy pentru a căuta fiecare grup de elemente cu valoarea 1. Algoritmul parcurge fiecare element din matrice și, dacă găsește un element cu valoarea 1 care nu a fost deja adăugat la un grup, apelează funcția dfs pentru a identifica toate elementele din același grup cu elementul respectiv.

1. 3 Funcția main citeste datele din fișierul grupuri.in, apelează funcția validare pentru a verifica dacă matricea de intrare este validă, apoi apelează funcția rezolvare pentru a număra grupurile de elemente cu valoarea 1. Dacă matricea nu este validă, scrie un mesaj de eroare în fișierul de ieșire grupuri.out, în caz contrar scrie numărul de grupuri de elemente cu valoarea 1 în fișierul grupuri.out.

1. 4 În ultima linie, __name__ =="main" verifică dacă fișierul curent este fișierul principal, apoi apelează funcția main dacă acesta este cazul.