查找矩阵中的面积数

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

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

如果两个“1”彼此相邻（仅水平和垂直），因此属于同一区域。我需要找出矩阵中有多少个这些区域。您可以看到该矩阵中有两个区域为“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;
}

一旦它遇到一个1，它递归地扩展到所有相邻的1元素，计算它们并将它们转化为0。如果该区域的大小大于IGN，然后将其考虑在内。

Notes:

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

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

• With IGN set to 1，单独的元素不被视为一个区域。改变IGN to 0也会得到那些。

• The if (A[j][i] == 1)循环中的条件并不是绝对必要的，但它可以通过避免不必要的函数调用来进行次要优化，尽管编译器优化可能会使其变得多余。

• 您可以轻松修改它以获得每个区域中的元素列表。