Page 41 - MATINF Nr. 9-10

Algoritmul fill s , i aplicat , ii 41

1. Citim m, n, elementele tabloului a s , i x0, y0 - linia s , i coloana pixelului interior conturului.

2. Din (x0,y0) gener˘am toate traseele cu metoda backtracking ˆın plan, f˘ar˘a a le memora,
doar marc˘am cu 1 elementele de pe aceste trasee. Cˆand ne g˘asim ˆıntr-un element a[i][j] putem s˘
a
ne deplas˘am numai ˆın cele 4 direct , ii: sus, dreapta, jos, stˆanga dac˘ elementele respective sunt 0.
a
a
Adic˘ ˆın a[i-1][j], a[i][j+1], a[i+1][j], a[i][j-1]. Pe scurt din a[i][j] ˆın a[in][jn], unde in = i + dl[k],
jn = j + dc[k], k = 0, 1, 2, 3, vectorii dl s , i dc memorˆand deplas˘arile relative ˆın cele 4 direct , ii:
int dl[4]={-1, 0, 1, 0};

int dc[4]={ 0, 1, 0,-1};

3. Dup˘ umplerea conturului ˆınchis se afis , eaz˘ tabloul.
a
a
Programul C++ pentru algoritmul de umplere a unui contur ˆınchis este prezentat ˆın
continuare.
#include <fstream >
using namespace std;

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

int a[200][200] ,m,n,x0 ,y0;
int dl[4]={ -1 , 0, 1, 0};
int dc [4]={ 0, 1, 0,-1};

void cit (){ // citirea imaginii si a coordonatelor unui pixel interior
int i,j;
fin >>m>>n;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
fin >>a[i][j];
fin >>x0 >>y0;
}

void fill(int i, int j){
int k,n,in ,jn;
a[i][j] = 1; // coloaram cu 1 pixelul curent din contur
for(k=0;k<4; k++){ // verificam pixeli vecini celui curent
in = i + dl[k];
jn = j + dc[k];
if(in >=1 && in <=m && jn >=1 && jn <=n && a[in][jn] == 0)
fill(in ,jn);
}
}

void afis (){ // afisarea tabloului bidimensional
int i,j;
for(i=1;i<=m;i++){
for(j=1;j<=n;j++)
fout <<a[i][j]<<" ";
fout <<endl;
}
}

int main (){
cit ();
fill(x0 ,y0);