Perimetrul insulelor într-o matrice, în C++

O celulă de uscat izolată are perimetrul 4. Două celule lipite pe o latură au împreună perimetrul 6, deoarece latura comună nu mai este expusă. Aria lor este 2; aria numără celule, perimetrul numără laturi.

Definim ce intră în perimetrul total

Citim 1≤n,m≤100 și o matrice cu valori 0 și 1. Valoarea 1 este uscat, 0 este apă. Fiecare celulă este un pătrat cu latura 1. Cerem numărul total al laturilor de uscat care ating apă sau ies în exteriorul matricei, pentru toate insulele la un loc.

În această definiție intră și marginile unui lac interior. Nu cerem doar conturul exterior al unei regiuni. Dacă enunțul ar exclude lacurile, ar trebui mai întâi să distingem apa conectată la exterior de apa închisă în uscat.

Verificăm patru laturi pentru fiecare 1

Pentru fiecare celulă de uscat, examinăm sus, dreapta, jos și stânga. Dacă vecinul este în afara matricei sau este apă, adăugăm unu. Dacă vecinul este uscat, latura este comună și nu contribuie.

Nu avem nevoie să identificăm separat fiecare insulă, deoarece adunăm toate laturile expuse. O parcurgere pe grupuri ar adăuga complexitate fără să ofere informație necesară acestei cerințe.

Celulele 1 din matricea 1,1 / 1,0 au 12 laturi în total. Două perechi vecine ascund câte două laturi, deci perimetrul este 8.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
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},perimetru=0;
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) if(a[i][j]==1) {
        for(int d=0;d<4;++d) {
            int x=i+di[d],y=j+dj[d];
            if(x<0 || x>=n || y<0 || y>=m || a[x][y]==0) ++perimetru;
        }
    }
    cout << perimetru << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
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 perimetru=0;
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) if(a[i][j]==1) {
        for(int d=0;d<4;++d) {
            int x=i+di[d],y=j+dj[d];
            if(x<0 || x>=n || y<0 || y>=m || a[x][y]==0) ++perimetru;
        }
    }
    cout << perimetru << '\n';
}

Ordinea condițiilor păstrează accesul valid

În condiția cu ||, adică „sau”, verificăm mai întâi ieșirea din matrice. Dacă oricare dintre aceste verificări este adevărată, C++ nu mai evaluează a[x][y]. Astfel nu citim o celulă cu coordonate invalide. Dacă am pune accesul primul, restul condiției nu l-ar mai putea proteja.

Tabloul clasic rezervă 100×100 celule, iar dreptunghiul folosit este n×m. Indicii sunt de la zero. Cele patru direcții sunt aceleași în varianta vector, care are exact n linii și m coloane.

Timpul este O(n·m), deoarece fiecare celulă de uscat verifică doar patru direcții. Starea suplimentară este O(1), fără coadă și fără matrice de vizitare. Intrarea memorată ocupă O(n·m) celule.

Exersează

Pentru 1 1 pe o singură linie, răspunsul este 6. Pentru 1 0 / 0 1, răspunsul este 8: atingerea pe diagonală nu elimină nicio latură. Un pătrat 2×2 plin are perimetrul 8. O matrice 3×3 plină, cu centrul zero, are perimetrul 16, incluzând cele patru laturi ale golului interior.

Continuă cu matrice și indici, conturul matricei și componente conexe.

Întrebări frecvente

Cum calculez perimetrul total al insulelor într-o matrice?

Pentru fiecare celulă de uscat, numără laturile care ating apă sau exteriorul matricei. Laturile comune cu alte celule de uscat nu contribuie la perimetru.

Care este diferența dintre aria și perimetrul unei insule?

Aria numără celulele de uscat, iar perimetrul numără laturile expuse. Două celule unite printr-o latură au aria 2 și perimetrul 6, nu 8.

Se numără și marginile unui lac interior?

Da în cerința acestei lecții, deoarece ele sunt laturi de uscat care ating apă. O problemă care cere numai conturul exterior ar necesita distingerea apei interioare de cea exterioară.