ALGORITMUL DE HASURARE A UNEI SUPRAFETE ÎNCHISE – FILL

Se dă o matrice binară (elementele egale cu 0 sau 1). Valorile 1 delimitează anumite suprafețe închise în cadrul matricei (elementele din interiorul acestor suprafețe sunt marcate cu 0). Fiind date coordonatele x și și y ale unui element al matricei, semnificând un punct în interiorul uneia dintre suprafețe, se cere să se hașureze suprafața care conține acest element.

S1 S2 Având suprafețele S1 și S2, în interiorul suprafeței S1 P1* se găsește punctul P1, se va hașura suprafața S1

De exemplu, dacă avem matricea: A=[0 10 0

1 1 00 0 1

0 00 0

1 1 01 0 0

] și considerăm în interiorul său

punctul de coordonate (2,3), atunci după executarea algoritmului FILL matricea va arăta astfel: A=

[1 11 1

1 1 01 1 1

1 11 1

1 1 01 0 0

].Pentru rezolvarea problemei, se folosește functia recursiva fill, care funcționează astfel:

- testează dacă elementul matricii ale cărui coordonate i-au fost transmise are valoarea 0;- dacă acest lucru este adevărat, atunci elementul respectiv va primi valoarea 1, iar funcția

se va autoapela pe rând pentru fiecare din vecinii acestui element (ortogonal = stânga, dreapta, sus, jos);

- dacă elementul este deja 1, atunci se revine din funcție.

Pentru a nu mai testa la fiecare pas dacă s-a ajuns la marginea matricei, este suficient să se bordeze matricea cu câte un rând de elemente egale cu 1.

#include<fstream>#include<iostream>using namespace std;

int a[20][20];int m,n,x,y;

void fill(int x, int y){

if(a[x][y]==0){

a[x][y]=1;fill(x+1,y);

fill(x,y+1);fill(x-1,y);fill(x,y-1);

}}

int main(){

fstream f,g;f.open("fill.in",ios::in);g.open("fill.out",ios::out);f>>m>>n>>x>>y;int i,j;for(i=1;i<=m;i++)

for(j=1;j<=n;j++)f>>a[i][j];

//bordare matricefor(i=1;i<=n;i++)

a[0][i]=a[m+1][i]=1;for(i=1;i<=m;i++)

a[i][0]=a[i][n+1]=1;g<<"Matricea initiala: "<<endl;for(i=1;i<=m;i++){

for(j=1;j<=n;j++)g<<a[i][j]<<' ';

g<<endl;}fill(x,y);g<<"Matricea finala: "<<endl;for(i=1;i<=m;i++){

for(j=1;j<=n;j++)g<<a[i][j]<<' ';

g<<endl;}f.close();g.close();

}

PROBLEMA FOTOGRAFIEI

Se dă o fotografie alb-negru, sub forma unei matrice bniare. Aceasta înfățișează unul sau mai multe obiecte. Elementele din matrice care aparțin unui obiect au valoarea 1. Să se determine câte

obiecte conține matricea și să se coloreze fiecare obiect cu o culoare diferită (elementele fiecărui obiect vor căpăta toate aceeași valoare, și nu există două obiecte care să fie colorate la fel).

De exemplu, în matricea alăturată avem un obierct, iar în următoarea trei obiecte.

A1= (0 1 0 01 0 0 10 1 1 0) A2= (

1 1 0 0 1 01 0 0 0 1 1011

010

1 0 0 10 1 0 01 0 1 0

)Pentru colorarea efectivă a unui obiect se folosește funcția obiect, care funcționează aproape la fel cu funcția fill. Prima deosebire dintre cele două este că în acest caz funcția va căuta pe toate cele 8 direcții posibile, deoarece și marginile unui obiect fac parte din acesta, iar cea de-a doua este că hașura nu se face tot în cadrul matricei inițiale, ci în cadrul unei matrice b, auxiliare. Astfel, în momentul întâlnirii unui punct care aparține obiectului curent, funcția îl va șetrge pe acesta din matricea inițială și îl va adăuga “colorat”, în matricea auxiliară b. în plus, această funcție primește ca argument și numărul cu care trebuie să “umple un anumit obiect.

Pentru a evita testul de depășire a marginilor matricei, aceasta se va borda cu elemente egale cu 0 (care nu aparțin niciunui obiect).

#include<fstream>#include<iostream>using namespace std;

int a[20][20], b[20][20];int m,n,nr;

void obiect(int x, int y, int nr){

if(a[x][y]==1){

a[x][y]=0;b[x][y]=nr;obiect(x,y+1,nr);obiect(x+1,y+1,nr);obiect(x+1,y,nr);obiect(x+1,y-1,nr);obiect(x,y-1,nr);obiect(x-1,y-1,nr);obiect(x-1,y,nr);obiect(x-1,y+1,nr);

}}

int main()

{fstream f,g;f.open("obiect.in",ios::in);g.open("obiect.out",ios::out);f>>m>>n;int i,j;for(i=1;i<=m;i++)

for(j=1;j<=n;j++)f>>a[i][j];

//bordare matricefor(i=0;i<=n+1;i++)

a[0][i]=a[m+1][i]=0;for(i=0;i<=m+1;i++)

a[i][0]=a[i][n+1]=0;g<<"Matricea initiala: "<<endl;for(i=1;i<=m;i++){

for(j=1;j<=n;j++)g<<a[i][j]<<' ';

g<<endl;}for(i=1;i<=m;i++)

for(j=1;j<=n;j++)if(a[i][j]==1){

nr++;obiect(i,j,nr);

}

g<<"Matricea finala: "<<endl;for(i=1;i<=m;i++){

for(j=1;j<=n;j++)g<<b[i][j]<<' ';

g<<endl;}f.close();g.close();

}