查找矩阵中的区域数 [英] Find number of areas in a matrix

问题描述

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

Assume I have a matrix something like this :

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

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

If two '1' are next to each other (horizontally and vertically only) and therefore belong to the same area. I need to find how many of these areas are there in a matrix. You can see that there's two areas of '1' in this matrix. I've been trying to solve this for hours now but the code gets really big and disgusting. Are there any algorithms out there I could adopt for this problem ?

推荐答案

如果您不太在意:

• 保持输入矩阵完整

• Keeping the input matrix intact

性能和优化

这是我对C语言中这个问题的看法:

then here's my take on this problem in 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，则将其考虑在内.

Once it encounters a 1, it recursively expands over all neighbouring 1 elements, counting them and turning them into 0. If the size of the area is larger than IGN, then it is taken into account.

注意:

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

• If you need to keep the original matrix, you would have to use a copy for input.

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

If you plan on using this, you should probably turn this code into functions that get the array and its size from their parameters. Global variables and algorithm implementations in main() should be avoided, but I made an exception in this case because it reduces the complexity of the code and allows the algorithm to be more clear.

在IGN设置为1的情况下，孤立元素不被视为区域.将IGN更改为0也会得到这些.

With IGN set to 1, lone elements are not considered an area. Changing IGN to 0 will get those too.

循环中的if (A[j][i] == 1)条件不是严格必需的，但是通过避免不必要的函数调用，它可以作为次要的优化，尽管编译器的优化可能会使它变得多余.

The if (A[j][i] == 1) conditional in the loop is not strictly necessary, but it serves as a minor optimisation by avoiding unnecessary function calls, although compiler optimisations probably make it redudant.

您可以轻松地对此进行修改，以获取每个区域中元素的列表.

You can easily modify this to get a listing of the elements in each area.

这篇关于查找矩阵中的区域数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！