c - 我需要找到递归的替代方法来解决这个问题

Question

注意:我更喜欢c语言的算法或代码，提前谢谢。

假设我有一个 5x5 二维数组。

00, 00, 01, 01, 00 
01, 00, 01, 01, 00 
01, 00, 00, 01, 01 
01, 01, 00, 00, 00 
01, 00, 00, 01, 01

分组标准:-数组中所有从上、下、左、右或对角线相连的1(01)属于同一组。

现在，我想在不递归的情况下将所有 1 (01) 组合在一起，使我的数组看起来像这样:-

00, 00, 02, 02, 00 
01, 00, 02, 02, 00 
01, 00, 00, 02, 02 
01, 01, 00, 00, 00 
01, 00, 00, 03, 03

最后我输出了有多少组。在这里，我输出 3。

假设我从一个索引位置找到连接，假设我在 i=1 和 j=0。现在使用嵌套循环，我可以从我所在的位置找到所有连接。

for(int i=-1; i<2; i++){
    for(int j=-1; j<2; j++){
}}

但是我如何从连接中找到连接呢？假设我从 i=1、j=0 找到所有连接。如果我在 i=1,j=1 处找到了 1 那么我该如何继续我的搜索呢？这里递归似乎很容易，但是如果没有递归我应该怎么做呢？

这是我目前所拥有的。我没有时间限制，所以我这样做很愚蠢。

void printImgArray(int array[L][L])
{
  
    printf("------ Image Contents -------\n");
    int i, j;
    for (i=0; i<L; i++)
    {
    for (j=0; j<L; j++)
        printf("%02d, ",array[i][j]);
    printf("\n");
    }
    printf("-----------------------------\n");
}

int checkIndex(int i, int j){
    return i >= 0 && j>=0 && i< L && j< L;
}

int colorNonRecursively(int image[L][L]) {
  int copyArray[L][L] = {0};
  int i, j, new_i, new_j;
  int counter = 1;

  for(i=0; i<L; i++){
    for(j=0; j<L; j++){
      for(new_i=-1; new_i<2; new_i++){
        for(new_j=-1; new_j<2; new_j++){
          if(copyArray[i][j] != 1 && image[i][j] != 0){
            copyArray[i][j] = 1;
            image[i][j] = counter;

            if(checkIndex(i+new_i, j+new_j)){
              if(copyArray[i+new_i][j+new_j] != 1 &&
                image[i+new_i][j+new_j] != 0){
                copyArray[i+new_i][j+new_j] = 1;
                image[i+new_i][j+new_j] = counter;
              }
            }
          }
        }
      }
      counter++;
    }
  }

int main(){

    int cellImg[L][L]={{0,0,1,1,0},\
                     {1,0,1,1,0},\
                     {1,0,0,1,1},\
                     {1,1,0,0,0},\
                     {1,0,0,1,1}};
    printImgArray(cellImg);
    colorNonRecursively(cellImg);
    printImgArray(cellImg);
    return 0;
}

输入二维数组:-

00, 00, 01, 01, 00 
01, 00, 01, 01, 00 
01, 00, 00, 01, 01 
01, 01, 00, 00, 00 
01, 00, 00, 01, 01

输出二维数组:-

00, 00, 03, 04, 00 
06, 00, 08, 09, 00 
11, 00, 00, 14, 15 
16, 17, 00, 00, 00 
21, 00, 00, 24, 25 

在这里，我可以看到我的计数器放置在正确的位置，但分组没有正确完成。我知道这段代码的运行时间为 N^4，但在我的例子中它并不重要，所以请忽略它。我怎样才能正确地将它们分组，以便我将这个数组作为输出？

输出二维数组(应该是):-

00, 00, 02, 02, 00, 
01, 00, 02, 02, 00, 
01, 00, 00, 02, 02, 
01, 01, 00, 00, 00, 
01, 00, 00, 03, 03, 

Answer 1

您可以创建该数组的图形表示，例如 1 是节点，边是相邻的 1。之后，您可以通过这些节点进行 DFS 搜索，并将它们标记为已完成的 DFS 搜索。因此，如果是第一次 DFS 搜索，则标签为 1，如果是第二次 DFS/BFS 搜索，则标签为 2，等等。请注意，DFS/BFS 搜索的数量是连通分量的数量。这样你就有了一个带有你想要的标签的图表。之后，您可以根据需要将图形转换为数组。这也可以扩展到 n 维。您可以使用迭代方法进行图形搜索。