Grade 12 · Grid algorithms: Lee and flood fillCitește în română

Islands in 8 directions

Original: Insule în 8 direcții

O(n²)C++1778 lines2 examples

The idea

Like counting regions, but two land cells (1) belong to the same island if they touch even at a corner, i.e. the neighbourhood has 8 directions. The only change is in the direction arrays, which now hold 8 pairs (dl, dc). For every unvisited 1 cell we count an island and erase it with a fill, using a queue.

Original description (Romanian)

Ca la numărarea zonelor, dar două celule de uscat (1) aparțin aceleiași insule dacă se ating și pe colț, adică vecinătatea are 8 direcții. Singura schimbare este în vectorii de deplasare, care au acum 8 perechi (dl, dc). Pentru fiecare celulă 1 nevizitată numărăm o insulă și o ștergem cu fill, folosind o coadă.

Complexity
O(n * m)
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input

4 5
1 0 0 1 0
0 1 0 0 1
0 0 0 0 0
1 1 0 0 1

Expected output

4
Example 2

Input

3 3
1 0 1
0 1 0
1 0 1

Expected output

1

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

insule-in-8-directii.cpp
/*
 * Titlu: Insule în 8 direcții
 * Clasa: 12
 * Capitol: Algoritmi pe grile: Lee și fill
 * Descriere: Ca la numărarea zonelor, dar două celule de uscat (1) aparțin
 *            aceleiași insule dacă se ating și pe colț, adică vecinătatea are 8
 *            direcții. Singura schimbare este în vectorii de deplasare, care au
 *            acum 8 perechi (dl, dc). Pentru fiecare celulă 1 nevizitată numărăm
 *            o insulă și o ștergem cu fill, folosind o coadă.
 * Complexitate: O(n * m)
 *
 * Exemplu
 * Intrare:
 * 4 5
 * 1 0 0 1 0
 * 0 1 0 0 1
 * 0 0 0 0 0
 * 1 1 0 0 1
 * Ieșire: 4
 *
 * Exemplu
 * Intrare:
 * 3 3
 * 1 0 1
 * 0 1 0
 * 1 0 1
 * Ieșire: 1
 */
#include <iostream>
#include <queue>
#include <utility>
using namespace std;

const int DIM = 1002;
int a[DIM][DIM];
int dl[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dc[8] = {0, 1, 1, 1, 0, -1, -1, -1};

void sterge(int i, int j)
{
    queue<pair<int, int>> q;
    a[i][j] = 0;
    q.push({i, j});
    while (!q.empty())
    {
        int l = q.front().first, c = q.front().second;
        q.pop();
        for (int k = 0; k < 8; k++)
        {
            int lv = l + dl[k], cv = c + dc[k];
            if (a[lv][cv] == 1)
            {
                a[lv][cv] = 0;
                q.push({lv, cv});
            }
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    int insule = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i][j] == 1)
            {
                insule++;
                sterge(i, j);
            }
    cout << insule << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.