Как эффективно найти области в двумерном массиве?

Question

Мне нужна идея, как эффективно найти области ниже, отмеченные 0 в двумерном массиве.Следует отметить, что существуют и другие области, например, на этом рисунке показана одна из двух, которой принадлежит координата (0.0), а другой - координата (21.3).

00000000000111110000111
00000000001111110000111
00000000011111100000111
00000000000111000001101
00000000011100000011101
00000001111100001111001
00000111111111011111001
00000001111100001111001
00000000010000000011001
00000000000000000001111

Конечно, реальный массив будет многобольше.Рекурсивная версия, которая идет во все стороны и останавливается на отметке 1 или стороне массива, не достаточно быстра.

Answer 1

Похоже, вы ищете алгоритм заливки .На странице википедии, на которую я ссылался, перечислены несколько алгоритмов, которые могут быть быстрее, чем очевидный рекурсивный метод.

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