Fill Algorithm

#include <iostream>

#define NMAX 500 // Schimbi in functie de dimensiunea maxima a lui N

using namespace std;

int matrice[NMAX][NMAX];
int vizitat[NMAX][NMAX];

/// Vectori de directii
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int N;

/// Algoritmul de umplere/fill
void umplere(int linie, int coloana)
{
    // Daca nici nu ma aflu in matrice, ies
    if(linie    < 0 || linie    >= N) return ;
    if(coloana  < 0 || coloana  >= N) return ;

    // Daca am ajuns pe un zero, nu trebuie sa continuam sau sa marcam
    if(matrice[linie][coloana] == 0)  return ;

    // Daca nu s-a oprit pana aici, inseamna ca:
    // 1) Ne aflam in matrice
    // 2) Ne aflam pe un 1
    // Deci trebuie sa marcam
    vizitat[linie][coloana] = 1;

    // Pentru fiecare directie
    // directie = 0 -> Sud
    // directie = 1 -> Est
    // directie = 2 -> Nord
    // directie = 3 -> Vest
    for(int directie = 0; directie < 4; ++directie)
    {
        // Calculez noile coordonate
        int linieNoua   = linie     + dx[directie];
        int coloanaNoua = coloana   + dy[directie];

        // Ma duc pe acea pozitie si o verific daca n-a fost verificata deja
        /// Daca ma duceam fara sa verific daca n-am mai fost, faceam o bucla infinita
        if(vizitat[linieNoua][coloanaNoua] == 0)
        {
            umplere(linieNoua, coloanaNoua);
        }
    }
}

int main() {
    cin >> N;

    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < N; ++j)
        {
            cin >> matrice[i][j];
        }
    }

    int nrComponente = 0;
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < N; ++j)
        {
            if(matrice[i][j] == 1 && vizitat[i][j] == 0)
            {
                // Inseamna ca am dat de o componenta noua
                // Daca vizitat ar fi fost 1, inseamna ca acest element (i, j) facea parte dintr-o alta componenta pe care am marcat-o

                umplere(i, j);
                ++nrComponente;
            }
        }
    }

    cout << nrComponente << '\n';

    return 0;
}