Algoritmi → Grafovi i stabla → Zadatak: Broj ostrva

Broj ostrva – zadatak i rešenje (BFS/DFS)

Zadatak

Mapa je matrica sa n vrsta i m kolona (n, m ≤ 1000): znak # je kopno, a . voda. Ostrvo je skup polja kopna povezanih po stranicama (gore, dole, levo, desno). Koliko ima ostrva i kolika je površina najvećeg?

4 5
##..#
#...#
..#..
.....

3
3

Ostrva su: {(0,0), (0,1), (1,0)} površine 3, {(0,4), (1,4)} površine 2 i {(2,2)} površine 1.

Ideja rešenja

Prolazimo kroz sva polja. Kad naiđemo na kopno koje još nije posećeno, našli smo novo ostrvo: povećamo brojač i iz tog polja pokrenemo BFS koji obeleži („potopi“) sva polja tog ostrva i prebroji ih. Svako polje se obeležava tačno jednom, pa je složenost O(n · m).

Rekurzivni DFS je kraći, ali za mapu 1000 × 1000 dubina rekurzije može dostići milion poziva i preliti stek – zato je ovde BFS sa redom.

Rešenje (C++)

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> mapa(n);
    for (auto &red : mapa) cin >> red;

    vector<vector<bool>> posecen(n, vector<bool>(m, false));
    int dr[] = {1, -1, 0, 0}, dk[] = {0, 0, 1, -1};
    int ostrva = 0, najvece = 0;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (mapa[i][j] != '#' || posecen[i][j]) continue;
            ostrva++;                                   // novo ostrvo
            int povrsina = 0;
            queue<pair<int, int>> red;
            red.push({i, j});
            posecen[i][j] = true;
            while (!red.empty()) {
                auto [r, k] = red.front();
                red.pop();
                povrsina++;
                for (int s = 0; s < 4; s++) {
                    int nr = r + dr[s], nk = k + dk[s];
                    if (nr < 0 || nr >= n || nk < 0 || nk >= m) continue;
                    if (mapa[nr][nk] != '#' || posecen[nr][nk]) continue;
                    posecen[nr][nk] = true;             // obeleži pri ubacivanju u red
                    red.push({nr, nk});
                }
            }
            najvece = max(najvece, povrsina);
        }
    cout << ostrva << "\n" << najvece << endl;
    return 0;
}

Polje se obeležava kao posećeno u trenutku ubacivanja u red, ne pri vađenju – inače bi isto polje moglo da uđe u red više puta.

Varijante

• Ako se računa i dijagonalno susedstvo, nizovi pomeraja imaju 8 elemenata.
• „Koliko ostrva ima posle svakog dodavanja kopna“ – tada se koristi Disjoint Set Union.
• Isti zadatak na sajtu LeetCode: Number of Islands.

Proveri znanje