Count Islands

Lab C++ Advanced 30 points

Read a grid of # (land) and . (water) and print the number of islands (4-connected land groups), using BFS with a queue.

Input

r c, then r rows.

Output

One integer.

Example

Input

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

Output

Sample input available Sample output available

Editor

C++

Hints

Each time you find unvisited land, BFS over the whole island and sink it.

Solution explanation

Counting connected components is a core graph technique.

Show solution

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

int main() {
    int r, c;
    cin >> r >> c;
    vector<string> g(r);
    for (auto &row : g) cin >> row;
    int islands = 0;
    int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (g[i][j] != '#') continue;
            islands++;
            queue<pair<int, int>> q;
            q.push({i, j});
            g[i][j] = '.';
            while (!q.empty()) {
                auto [y, x] = q.front();
                q.pop();
                for (int d = 0; d < 4; d++) {
                    int ny = y + dr[d], nx = x + dc[d];
                    if (ny >= 0 && ny < r && nx >= 0 && nx < c && g[ny][nx] == '#') {
                        g[ny][nx] = '.';
                        q.push({ny, nx});
                    }
                }
            }
        }
    }
    cout << islands << "\n";
    return 0;
}

Output

Answer