Algoritmul de fill

Intuiția

Imaginează-ți o hartă cu insule: 1 e uscat, 0 e apă. Dacă pui degetul pe o celulă de uscat, poți „atinge" toată insula mutându-te doar la vecini de uscat (sus, jos, stânga, dreapta). Apa te oprește — exact ca marginea în Paint.

Un fill pornit dintr-o celulă marchează întreaga insulă din care face parte. Deci, ca să afli câte insule sunt, pornești un fill din fiecare celulă de uscat încă neatinsă și numeri câte fill-uri ai pornit.

Vezi cum funcționează

Urmărește cum vopseaua se extinde celulă cu celulă din punctul de start spre toți vecinii de același fel, marcându-i ca vizitați, oprindu-se la graniță. Aici ne interesează exact acest mecanism de răspândire — nu lungimea unui drum, ci cât prinde o singură pornire. Apoi citește mai jos de ce fiecare fill prinde exact o insulă.

Algoritmul pas cu pas

Fie matricea de 4x4 (unde 1 = uscat, 0 = apă):

Parcurgem rând cu rând, de la stânga la dreapta. Întâlnim prima celulă 1 la (r0,c0). E nevizitată → insula 1, pornim un fill de aici.

Fill-ul pleacă din (r0,c0), îl marchează (scriem * pentru o celulă marcată), apoi se mută la vecinii de uscat și îi marchează și pe ei:

• (r0,c0) → marcat. Vecini de uscat: (r0,c1) și (r1,c0).
• (r0,c1) → marcat. Vecini noi de uscat: niciunul (dreapta (r0,c2) e apă, jos (r1,c1) e apă).
• (r1,c0) → marcat. Vecini noi de uscat: niciunul (jos (r2,c0) e apă, dreapta (r1,c1) e apă).

Componenta s-a închis. Insula 1 = $\{(r0,c0), (r0,c1), (r1,c0)\}$ → 3 celule marcate:

Continuăm parcurgerea. Următorul 1 nevizitat e la (r1,c3). → insula 2, pornim un fill. Toți vecinii lui sunt apă (sus, jos, stânga), deci insula are o singură celulă. Insula 2 = $\{(r1,c3)\}$ → 1 celulă:

Mergem mai departe. Următorul 1 nevizitat e la (r2,c2). → insula 3, fill:

• (r2,c2) → marcat. Vecin de uscat jos: (r3,c2).
• (r3,c2) → marcat. Vecin de uscat dreapta: (r3,c3).
• (r3,c3) → marcat. Vecini noi de uscat: niciunul.

Insula 3 = $\{(r2,c2), (r3,c2), (r3,c3)\}$ → 3 celule:

Restul parcurgerii întâlnește doar 0-uri sau celule deja marcate. Contorul s-a incrementat de 3 ori → matricea are 3 insule. Observă: deși are 7 celule de uscat, sunt grupate în doar 3 componente conexe.

Implementare C++

Fill recursiv (DFS) pe 4 direcții. Bucla din main pornește un fill pentru fiecare celulă de uscat nevizitată și numără insulele:

#include <iostream>
using namespace std;

int L = 4, C = 4;                 // dimensiunile matricei
int a[4][4] = {                   // 1 = uscat, 0 = apa
    {1, 1, 0, 0},
    {1, 0, 0, 1},
    {0, 0, 1, 0},
    {0, 0, 1, 1}
};

// fill: marcheaza toata insula care contine (i, j)
void fill(int i, int j) {
    // ies daca am parasit matricea sau am dat de apa / celula vizitata
    if (i < 0 || i >= L || j < 0 || j >= C) return;
    if (a[i][j] != 1) return;     // 0 = apa, sau deja marcat cu 2

    a[i][j] = 2;                  // MARCHEZ inainte de a cobori in vecini

    fill(i - 1, j);               // sus
    fill(i + 1, j);               // jos
    fill(i, j - 1);               // stanga
    fill(i, j + 1);               // dreapta
}

int main() {
    int insule = 0;
    for (int i = 0; i < L; i++) {
        for (int j = 0; j < C; j++) {
            if (a[i][j] == 1) {   // celula de uscat inca nevizitata
                insule++;         // insula noua
                fill(i, j);       // marcheaza toata insula ei
            }
        }
    }
    cout << insule << endl;       // 3
    return 0;
}

Marcăm cu 2 (nu cu 0) ca să distingem „uscat vizitat" de „apă"; oricum, după parcurgere, condiția a[i][j] == 1 din main nu mai e adevărată pentru celulele deja inundate. La matrice foarte mari, recursia poate da stack overflow — atunci înlocuiești recursia cu o coadă (BFS): scoți o celulă, o marchezi și îi adaugi în coadă vecinii de uscat nevizitați. Logica de numărare rămâne identică.

Complexitate

Fie L linii și C coloane. Fiecare celulă e vizitată o singură dată (la a doua vizită e deja marcată și fill-ul se întoarce imediat):

Timpul e liniar în numărul de celule. Spațiul vine din stiva de apeluri (sau din coadă la BFS), care în cel mai rău caz — o singură insulă ce umple toată matricea — ține toate cele L · C celule.