查找矩阵中的区域数量

Question

假设我有一个像这样的矩阵:

1 1 1 0 0 0
1 1 1 0 0 1
0 0 0 0 0 1

如果两个'1'彼此相邻(仅水平和垂直),因此属于同一区域.我需要找到矩阵中有多少这些区域.您可以看到此矩阵中有两个"1"区域.我一直试图解决这个问题几个小时,但代码变得非常大而令人作呕.我有什么算法可以解决这个问题吗？

Answer 1

如果你真的不在乎:

• 保持输入矩阵完整

• 性能和优化

那么这是我在C中对这个问题的看法:

#include <stdio.h>

#define X       8
#define Y       4

#define IGN     1

int A[Y][X] = {
        { 1, 1, 1, 0, 0, 0, 0, 1 },
        { 1, 1, 1, 0, 0, 1, 0, 1 },
        { 0, 0, 0, 0, 0, 1, 0, 1 },
        { 0, 0, 0, 0, 0, 1, 1, 1 },
};

int blank(int x, int y) {
        if ((x < 0) || (x >= X) || (y < 0) || (y >= Y) || (A[y][x] == 0))
                return 0;

        A[y][x] = 0;

        return 1 + blank(x - 1, y) + blank(x + 1, y) + blank(x, y - 1) + blank(x, y + 1);
}

int main() {
        int areas = 0;

        int i, j = 0;

        for (i = 0; i < X; ++i)
                for (j = 0; j < Y; ++j)
                        if (A[j][i] == 1)
                                if (blank(i, j) > IGN)
                                        areas++;

        printf("Areas: %i\n", areas);

        return 0;
}

一旦遇到a 1,它会递归地扩展所有相邻1元素,计算它们并将其转换为0.如果该区域的大小大于IGN,则将其考虑在内.

笔记:

• 如果您需要保留原始矩阵,则必须使用副本进行输入.

• 如果您打算使用它,您应该将此代码转换为从其参数获取数组及其大小的函数.main()应避免使用全局变量和算法实现,但在这种情况下我做了一个例外,因为它降低了代码的复杂性并使算法更加清晰.

• 随着IGN集来1,孤独的元素不被视为一个区域.更改IGN到0会得到这些呢.

• if (A[j][i] == 1)循环中的条件并不是绝对必要的,但它通过避免不必要的函数调用作为次要优化,尽管编译器优化可能使其减少.

• 您可以轻松修改此选项以获取每个区域中元素的列表.