2: FillAlgoritmul FILL realizeaz umplerea (colorarea) unei suprafee nchise. Considerm o matrice ale crei elemente pot avea una dintre valorile 1 i 0 cu semnificaia: 1 reprezint un perete, iar 0 o zon liber.Pornind dintr-o zon de valoare 0, algoritmul trebuie s coloreze cu valoarea 2 toate celelalte celule n care se poate ajunge mergnd un numr finit de pai pe direciile: sus, jos, stnga, dreapta.Pentru simplitate, considerm c matricea este bordat cu elemente a cror valoare este 1 (bordarea unei matrice N*M nseamn punerea unei valori la exteriorul acesteia, adic pe liniile 0 si N+1 i pe coloanele 0 i M+1, pentru a nu iei din interiorul matricei).

Implementarea poate fi fcut recursiv sau cu ajutorul unei cozi. Este de preferat s folosim o coad, deoarece pentru N i M cu valori mari, un FILL recursiv poate depi limita de memorie a stivei (ceea ce nseamn 0 puncte pe testele mari).

Fie coadax i coaday dou cozi n care vom memora liniile, respectiv coloanele. Dac pornim din punctul x0, y0 i vrem s vedem dac putem ajunge n xf, yf, atunci vom proceda n felul urmator:1. Introducem x0 n coadax i y0 n coaday.2. Parcurgem coada pn cnd aceasta devine vid.3. La fiecare pas adugm n coad noile coordonate n care e posibil deplasarea (pentru o pereche de coordonate x i y, verificm dac M[x][y-1], M[x][y+1], M[x-1][y] i M[x+1][y] sunt egale cu 0 i nu au fost deja adugate n coad, pentru c altfel programul ar rula la infinit) i scoatem din coad elementul curent.4. Verificm dac n urma executrii algoritmului FILL poziia (xf, yf) a fost vizitat.

Complexitata algoritmului FILL este T(N*M).

(Opional) Elemente de STL:#include // este biblioteca ce trebuie inclus pentru a folosi coada din STLqueue nume_coada; // de exemplu, pentru o coad de numere ntregi vom declara // queue coada;coada.push(x); // insereaza elementul x n coadcoada.pop(); // terge primul element din coadcoada.empty() // returneaza true, dac este vid coada i false n caz contrarcoada.front() // returneaza primul element din coad