Numărarea insulelor într-o matrice: flood fill C++

O insulă este un grup de celule cu valoarea 1 conectate prin laturi. Celulele cu 0 reprezintă apă. Numărăm câte grupuri separate există. În limbajul grafurilor, un astfel de grup se numește componentă conexă: din orice celulă a lui putem ajunge în oricare alta mergând numai prin celule de uscat vecine. Nu trebuie să construim explicit un graf; folosim direct matricea.

Vecinătatea schimbă răspunsul

În această lecție permitem numai sus, dreapta, jos și stânga. Pentru matricea 1 0 / 0 1, răspunsul este 2. Dacă am permite și diagonalele, ar fi 1. Nu alege vecinătatea din obișnuință: ea face parte din cerință.

Citim 1 ≤ n,m ≤ 100, apoi n·m valori egale cu 0 sau 1, separate prin spații. Afișăm numărul insulelor. Tabloul clasic are capacitatea 100×100; doar dreptunghiul n×m reprezintă date. Coordonatele interne sunt de la zero.

Ce înseamnă BFS și cum folosim o coadă

BFS vine de la Breadth-First Search și înseamnă parcurgere în lățime. Pornim dintr-o celulă de uscat, vizităm mai întâi vecinii ei, apoi vecinii încă nevizitați ai acestora. Repetăm până când am descoperit întregul grup. Procedeul de a umple sau marca o zonă conectată se numește și flood fill.

O coadă păstrează celulele care așteaptă să fie prelucrate, în ordinea descoperirii. Prima celulă introdusă este prima extrasă, la fel ca într-o coadă la magazin. În cod, q.push({i,j}) adaugă coordonatele la sfârșit, q.front() citește prima pereche, q.pop() o elimină, iar q.empty() verifică dacă mai avem celule de prelucrat. pair<int,int> ține împreună indicele liniei și al coloanei.

De exemplu, pentru liniile 1 1 0, 0 1 0, 1 0 1, pornim din (0,0). Coada conține inițial doar această celulă. La extragere descoperim (0,1), iar din ea descoperim (1,1). După prelucrarea celor trei celule, coada se golește: prima insulă este complet marcată. Celulele (2,0) și (2,2) sunt două insule separate, deoarece atingerea pe diagonală nu contează.

Celulele (0,0),(0,1),(1,1) formează prima insulă. (2,0) și (2,2) sunt insule separate. Coada parcurge primul grup în această ordine.Mărește schema ↗

O parcurgere pentru fiecare insulă nouă

Scanăm toate celulele. Când întâlnim un 1 încă nemarcat, am descoperit o insulă nouă. Pornim BFS din el și transformăm în 0 toate celulele de uscat accesibile. Când scanarea ajunge la altă celulă a aceleiași insule, ea este deja marcată și nu mărește contorul.

Marcăm o celulă chiar înainte de introducerea în coadă. Dacă am marca-o abia la extragere, mai mulți vecini ar putea introduce aceeași celulă de mai multe ori.

Varianta cu tablou clasic

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
int main() {
    int n,m; cin >> n >> m;
    int a[100][100];
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) cin >> a[i][j];
    int di[4]={-1,0,1,0}, dj[4]={0,1,0,-1};
    int insule=0;
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) if(a[i][j]==1) {
        ++insule; queue<pair<int,int>> q;
        a[i][j]=0; q.push({i,j});
        while(!q.empty()) {
            auto [x,y]=q.front(); q.pop();
            for(int d=0;d<4;++d) {
                int nx=x+di[d], ny=y+dj[d];
                if(nx>=0 && nx<n && ny>=0 && ny<m && a[nx][ny]==1) {
                    a[nx][ny]=0; q.push({nx,ny});
                }
            }
        }
    }
    cout << insule << '\n';
}

Varianta echivalentă cu std::vector

Indicii și datele de intrare rămân aceleași. Containerul este construit cu numărul de elemente folosite; accesul prin [] cere în continuare indici valizi.

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
int main() {
    int n,m; cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) cin >> a[i][j];
    vector<int> di={-1,0,1,0}, dj={0,1,0,-1};
    int insule=0;
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) if(a[i][j]==1) {
        ++insule; queue<pair<int,int>> q;
        a[i][j]=0; q.push({i,j});
        while(!q.empty()) {
            auto [x,y]=q.front(); q.pop();
            for(int d=0;d<4;++d) {
                int nx=x+di[d], ny=y+dj[d];
                if(nx>=0 && nx<n && ny>=0 && ny<m && a[nx][ny]==1) {
                    a[nx][ny]=0; q.push({nx,ny});
                }
            }
        }
    }
    cout << insule << '\n';
}

De ce numărăm exact componentele

BFS vizitează numai celule unite prin laturi cu punctul de pornire, deci nu unește două insule diferite. În același timp, orice celulă conectată printr-un drum de uscat va fi descoperită pas cu pas. O parcurgere epuizează exact o insulă. Scanarea pornește următoarea parcurgere numai dintr-o componentă încă nevizitată.

Ordinea verificărilor din condiție contează: întâi validăm coordonatele, apoi accesăm a[nx][ny]. Operatorul && oprește evaluarea când o condiție este falsă, protejând accesul la vecinii din afara matricei.

Timpul este O(n·m), deoarece fiecare celulă intră cel mult o dată în coadă și are patru vecini de verificat. Memoria suplimentară poate ajunge la O(n·m) pentru coadă. Modificăm matricea; dacă trebuie reutilizată, păstrează o matrice separată de vizitare sau o copie.

Exersează

Testează o matrice numai cu zero, una numai cu unu și exemplul diagonal 2×2. Răspunsurile sunt 0, 1 și 2. Pentru liniile 1 1 0, 0 1 0, 1 0 1, sunt trei insule.

Extinde BFS pentru aria fiecărei insule: numără celulele extrase din coadă și păstrează maximul. Pentru ultimul exemplu, aria maximă este 3. Nu număra vecinii de apă ca parte a ariei.

Continuă cu parcurgerea în lățime și parcurgerea în adâncime, componente conexe și coordonatele matricelor.

Întrebări frecvente

Ce înseamnă BFS la numărarea insulelor?

BFS înseamnă Breadth-First Search, adică parcurgere în lățime. Folosește o coadă pentru a vizita celulele de uscat conectate cu punctul de pornire, procesând mai întâi celulele descoperite mai devreme.

Celulele de uscat unite pe diagonală formează aceeași insulă?

Nu în această lecție. Sunt permise numai legăturile prin laturi: sus, jos, stânga și dreapta. În matricea cu liniile 1 0 și 0 1 există două insule.

De ce marchez celula înainte să o introduc în coada BFS?

Marcarea la descoperire împiedică alți vecini să introducă aceeași celulă din nou. Fiecare celulă este astfel procesată cel mult o dată, iar numărarea tuturor insulelor are timp O(n·m).