Rezolvare PBinfo #1507

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:

grupuri.in

4
1 0 0 1
0 0 1 1
0 1 0 1
1 1 0 0

grupuri.out

3

Explicație

Cele trei grupuri din fişierul de intrare sunt (considerând matricea indexată de la 1 la n):
G1 = {(1, 1)}
G2 = {(1, 4), (2, 3), (2, 4), (3, 4)}
G3 = {(3, 2), (4, 1), (4, 2)}