How to effectively find areas in two-dimensional array?

Question

I need an idea how to effectively find areas below marked with 0 in two-dimensional array. It should be noted that there are other areas, such as this picture shows one of two who owns coordinate (0.0) and the other owns coordinate (21.3).

00000000000111110000111
00000000001111110000111
00000000011111100000111
00000000000111000001101
00000000011100000011101
00000001111100001111001
00000111111111011111001
00000001111100001111001
00000000010000000011001
00000000000000000001111

Of course a real array will be much larger. Recursive version that goes to all sides and stops at mark 1 or array side isn't fast enough.

Answer 1

It looks like you're looking for a flood-fill algorithm. The wikipedia page I linked lists a few algorithms which may be faster than the obvious recursive method.

Flood-fill will be a good match if the areas you're looking for are small compared to the entire array, and you don't need to search for all of them. If you need to know about most or all of them, then computing them all in a single shot using a union-merge based connected component labeling algorithm may be a better choice. Here's some code that implements such an algorithm (note that I've altered it to run in a single pass):

#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;
}