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):
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)}
#include <bits/stdc++.h>
using namespace std;
ifstream cin("grupuri.in");
ofstream cout("grupuri.out");
int a[102][102];
void fill(int i, int j, int c)
{
a[i][j] = c;
if(a[i-1][j] == 1)
fill(i-1, j, c);
if(a[i][j+1] == 1)
fill(i, j+1, c);
if(a[i+1][j] == 1)
fill(i+1, j, c);
if(a[i][j-1] == 1)
fill(i, j-1, c);
}
int main()
{
int n, c = 0;
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <=n; j++)
cin >> a[i][j];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(a[i][j] == 1)
{
c++;
fill(i, j, c + 1);
}
cout << c;
return 0;
}
