c - 在二维数组中找到最大的簇

Question

我必须在二维数组中找到一个簇。这意味着我必须在二维数组中找到最大数量的“1”。数组中只有“0”和“1”。相连的数字在每个方向(8个方向)可以全为“1” 例如这个矩阵有一簇 6

示例:输出 = 6

ma[] = { 1, 1, 0, 0, 0,
         1, 1, 0, 0, 0,
         0, 0, 1, 0, 0,    //because of diagonal
         0, 1, 0, 0, 1 };   // the last "1" should not be counted 

不幸的是，我不知道该怎么做。这是我最新的代码，我可以用它计算二维数组中的所有“1”。

void cluster(int *mat, int rows, int cols) { 
    int i, j;
    int target = 0;
    printf("\n+++++++++++++++++++++++++++++++\nbiggst cluster\n\n");
    for(j = 0; j < cols; j++) { 
        for (i = 0; i < rows; i++) {
        if (mat[j*rows+i] == 1)
        target = target + 1;
        }
    }
printf("%d ", target);
}

我真的很感激一个小代码或算法来解决这个问题。

问候

Answer 1

可以通过首先定义和陈述目标，然后将其分解为解决问题所需的步骤来解决问题:

首先，对您的问题陈述进行一些澄清:

下面的没有定义二维矩阵，它被创建为一个包含 20 个元素的单维数组

ma[] = { 1, 1, 0, 0, 0,
         1, 1, 0, 0, 0,
         0, 0, 1, 0, 0,    //because of diagonal
         0, 1, 0, 0, 1 };   // the last "1" should not be counted 

二维数组中“1”的最大数量
假设您的意思是，数组中值== 1 的相邻元素的数量
和
每个方向(8 个方向)的数字可以全为“1”
C 数组中确实只有两个方向。 (解释见下文)

为清楚起见，修改一些定义:
1) 定义一组值:
簇是包含值 1 的 1 个或多个数组元素，并且在任何方向上相邻到另一个数组元素。 (请参阅下面对 adjacent 的评论)
2) 在C中定义一个二维数组: C 中的二维数组是连续内存区域，其中数组元素以行主要方式排列:

Example: int array[4][5] = {{1,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0}};  

概念上看起来像这样:

|1|0|0|0|0|    
|0|1|0|0|0|     
|0|0|1|0|0|    
|0|0|0|1|0|  //cluster of four

但在内存中是这样的:

|1|0|0|0|0|0|1|0|0|0|0|0|1|0|0|0|0|0|1|0|  //cluster of zero  (no "1" elements next to another)
|         |         |         |       |              
[0][0]    [1][0]    [2][0]    [3][0]  [3][4]      

请注意，实际上，Adjacent 具有不同的视角。

所以预期的解决方案与相邻内存关系不大，更多的是与数组表示法有关，例如[i][j] .

为了您的目的，adjacent 应该定义为:
元素索引的接近度，其中另一个元素在任何方向上最多相距 1 个索引:

给定整数 array[ROWS][COLS];

这是一个邻接测试:(使用我们的定义)

array[m][n]毗邻array[o][p]时间:

• !((m == o) && (n == p)) //same element
• (abs(m - o) <= 1) && (abs(n-p) <= 1)
• ((m + o) < ROWS) &&((n + p) < COLS)

这个问题可以通过逐行遍历所有元素来解决，在每个元素处，通过查看每个周围的索引来测试与另一个元素的接近度。