Page 44 - MATINF Nr. 9-10

44 D.A. Popescu, D. Constantin

1 1 0 0 1 1 0 0
1 1 0 0 1 0 1 0
1 0 0 0 0 0 0 1

foto2.out

4

Descrierea algoritmului

1. Citim m, n s , i elementele tabloului a.

2. Parcurgem elementele tabloului a cu i=1,...,m s , i j =1,2,...,n, dac˘a a[i][j]=1 num˘ar˘am
obiectul curent s , i ˆıl s , tergem cu apelul fill(i,j).

3. Afis , ˘am num˘arul de obiecte.
Programul C++ pentru algoritm este urm˘atorul:

#include <fstream >
using namespace std;

ifstream fin("foto2.in");
ofstream fout("foto2.out");

int a[200][200] ,m,n,NrOb;
int dl[8]={-1,-1, 0, 1, 1, 1, 0,-1};
int dc [8]={ 0, 1, 1, 1, 0,-1,-1,-1};

void cit (){
int i,j;
fin >>m>>n;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
fin >>a[i][j];
}
void fill(int i, int j){
int k,n,in ,jn;
a[i][j] = 0;
for(k=0;k<8; k++){
in = i + dl[k];
jn = j + dc[k];
if(in >=1 && in <=m && jn >=1 && jn <=n && a[in][jn] == 1)
fill(in ,jn);
}
}

int main (){
cit ();
int i,j;
NrOb = 0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(a[i][j]==1){
NrOb ++;
fill(i,j);
}
fout <<NrOb;
return 0;
}