Page 39 - MATINF Nr. 9-10

Algoritmul fill si aplicatii
,
,

1
Doru Anastasiu Popescu s , i Doru Constantin 2

ˆ a a a
In acest articol se prezint˘ algoritmul fill de tip backtracking ˆın plan ˆıntr-o manier˘ simpl˘
cu structuri de date elementare. Apoi, sunt prezentate cˆateva probleme clasice rezolvate cu acest
ˆ
a
algoritm. In partea final˘ a articolului s-a introdus o list˘ de probleme din arhive educat , ionale
a
pentru a implementa algoritmul fill ˆın situatii variate.

1 Introducere

ˆ
Algoritmul fill este un caz particular de parcurgere a unui graf neorientat. In acest articol se
a
a
prezint˘ algoritmul f˘ar˘ a se folosi not , iuni de teoria grafurilor. Mai precis, vom porni de la un
caz practic legat de aplicat , ia Paint. Fiecare dintre noi a creat un desen ˆın aplicat , ia Paint s , i a
a
a
trebuit s˘ umple cu o anumit˘ culoare un contur ˆınchis (cerc, dreptunghi, triunghi, etc). Acest
lucru l-am realizat selectˆand culoarea, pensula s , i dˆand click ˆın interiorul conturului. Apoi instant
operat , ia a fost realizat˘a. Lucrul acesta s-a realizat pentru c˘ ˆın spatele aplicat , iei imaginea este
a
un tablou bidimensional, elementele lui fiind pixeli de o anumit˘a culoare, s , i cu un algoritm
ˆ
de tip fill se schimb˘a culoarea pixelilor din interiorul conturului. In Figura 1 s , i Figura 2 este
prezentat un astfel de exemplu.

Figura 1. Contururi umplute cu culori ˆın Paint.

1
Conf. univ. dr., Universitatea din Pites , ti, dopopan@yahoo.com
2
Conf. univ. dr., Universitatea din Pites , ti, cdomanid@yahoo.com
39