How to efficiently find areas in a two-dimensional array?

Question

I need an idea how to efficiently find areas below marked 0 in a two-dimensional array. It should be noted that there are other areas, such as this figure shows one of the two, which belongs to the coordinate (0.0), and the other belongs to the coordinate (21.3).

00000000000111110000111
00000000001111110000111
00000000011111100000111
00000000000111000001101
00000000011100000011101
00000001111100001111001
00000111111111011111001
00000001111100001111001
00000000010000000011001
00000000000000000001111

Of course, the real array will be much larger. The recursive version, which comes from all directions and stops at 1 or on the side of the array, is not fast enough.

Answer 1

, . wikipedia, , , , .

Flood-fill , , , , . , . , ( , ):

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <map>

const char *data[] = {
"00000000000111110000111",
"00000000001111110000111",
"00000000011111100000111",
"00000000000111000001101",
"00000000011100000011101",
"00000001111100001111001",
"00000111111111111111001",
"00000001111100001111001",
"00000000010000000011001",
"00000000000000000001111",
NULL
};

struct label {
private:
    int index;
    int rank;
    label *parent;
public:
    label ()
        : index(-1), rank(0), parent(this)
    { }

    int getIndex(int &maxIndex) {
        if (parent != this)
            return find()->getIndex(maxIndex);

        if (index < 0)
            index = maxIndex++;
        return index;
    }

    label *find() {
        if (parent == this)
            return this;

        parent = parent->find();
        return parent;
    }

    label *merge(label *other)
    {
        label *xRoot = find();
        label *yRoot = other->find();

        if (xRoot == yRoot)
            return xRoot;

        if (xRoot->rank > yRoot->rank) {
            yRoot->parent = xRoot;
            return xRoot;
        } else {
            xRoot->parent = yRoot;
            if (xRoot->rank == yRoot->rank)
                yRoot->rank++;
            return yRoot;
        }
    }
};

int width, height;

int main() {
    for (int i = 0; data[0][i]; i++)
        width = i + 1;
    for (int i = 0; data[i]; i++) {
        height = i + 1;
    }

    std::vector<std::vector<unsigned short> > lblinfo;
    lblinfo.resize(height, std::vector<unsigned short>(width, 0));

    std::vector<label *> labels;
    labels.push_back(NULL); // 0 is used as an unassigned flag

    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            if (data[y][x] == '1')
                continue;

            // Try to find a neighboring label
            unsigned short lblid = 0;
            if (x != 0 && lblinfo[y][x-1] != 0)
                lblid = lblinfo[y][x-1];

            // merge with cells above
            if (y != 0) {
                for (int x2 = x - 1; x2 <= x + 1; x2++) {
                    if (x2 < 0)
                        continue;
                    if (x2 >= width)
                        continue;

                    unsigned short otherid = lblinfo[y - 1][x2];
                    if (!otherid)
                        continue;

                    if (!lblid)
                        lblid = otherid;
                    else {
                        labels[lblid]->merge(labels[otherid]);
                    }
                }
            }

            if (!lblid) {
                // assign a new label
                lblid = labels.size();
                labels.push_back(new label);
            }
            lblinfo[y][x] = lblid;
        }
    }

    // Assign indices to the labels by set and print the resulting sets
    int maxindex = 0;
    static const char chars[] = "abcefghijklmnopqrstuvwxyz";
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            unsigned short labelid = lblinfo[y][x];
            if (labelid == 0) {
                putchar(data[y][x]);
                continue;
            }

            label *label = labels[labelid];
            int idx = label->getIndex(maxindex);
            if (idx >= sizeof(chars) - 1) {
                printf("\n\n Too many labels to print!\n");
                exit(1);
            }

            putchar(chars[idx]);
        }
        printf("\n");
    }

    return 0;
}