如何有效地在二维数组中查找区域？

Question

如何有效地在二维数组中查找区域？

5

我需要一个方法来有效地查找二维数组中标记为0的区域。需要注意的是，还有其他区域，例如这张图片显示了其中一个拥有坐标（0.0）的区域和另一个拥有坐标（21.3）的区域。

00000000000111110000111
00000000001111110000111
00000000011111100000111
00000000000111000001101
00000000011100000011101
00000001111100001111001
00000111111111011111001
00000001111100001111001
00000000010000000011001
00000000000000000001111

当然，一个真正的数组会大得多。递归版本可以遍历所有的方向，并在遇到标记1或数组边缘时停止，但速度不够快。

- Trac3

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bdonlan · Accepted Answer

看起来你正在寻找泛洪算法。我链接的维基百科页面列出了一些可能比显而易见的递归方法更快的算法。

如果你要查找的区域相对于整个数组很小，并且你不需要搜索所有区域，那么泛洪算法将是一个很好的选择。如果你需要知道大部分或全部区域的信息，则使用基于联合并的连通分量标记算法一次性计算它们可能是更好的选择。这里有一些实现这种算法的代码（注意我已经修改它以在单次运行中运行）：

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