C-列出矩阵中相同数字的最大邻域

Question

我是编程新手。我知道我的问题可能不是很聪明，但请耐心等待。我提到这不是作业。

我想找出附近的数量，每个由多少个 1 组成，以及每个附近最左上角的单元格的坐标。

例如，对于以下矩阵:

{1, 1, 1, 0, 1}
{0, 0, 1, 0, 1}
{0, 1, 1, 0, 0}
{0, 0, 0, 0, 0}

在这个例子中有两组 1。第一个有六个 1，第二个有两个 1。

我在下面贴出到目前为止的源代码。它只为某些矩阵打印正确答案，因为我的代码只检查 1 的向上一个字段、向下一个字段、向右一个字段和向左一个字段。我想知道如何在不使用递归方法的情况下摆脱这个问题。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define m 4
#define n 5

int Check(int A[][100],int i,int j,int Checked[][100])
{
    if(A[i][j]==1 && Checked[i][j]==0)
    {
        Checked[i][j]=1;
        return 1;
    }
    return 0;
}

int main()
{
    int A[100][100],i,j,Checked[100][100],begin=0;
    int counter=0;
    int base[100];
    int k=0,x=0;
    int lines[100],cols[100];

srand(time(NULL));

for(i=0;i<m;i++)//generating random matrix
{
    for(j=0;j<n;j++)
    {
        A[i][j]=rand()%2;
        printf("%d ",A[i][j]);
    }
    printf("\n");
}

for(i=0;i<m;i++)//initialising with 0 the Checked matrix
{
    for(j=0;j<n;j++)
    {
        Checked[i][j]=0;
    }
}

for(i=0;i<m;i++)
{
    for(j=0;j<n;j++)
    {
        if(Checked[i][j]==0)
        {
            Checked[i][j]=1;

            if(A[i][j]==1 && begin==0)
            {
                lines[x]=i;
                cols[x]=j;
                begin=1;
                x++;
                counter++;
            }
            if(A[i][j]==1)
            {
                if(Check(A,i-1,j,Checked)==1)
                    counter++;
                if(Check(A,i,j+1,Checked)==1)
                    counter++;
                if(Check(A,i+1,j,Checked)==1)
                    counter++;
                if(Check(A,i,j-1,Checked)==1)
                    counter++;
                if(Check(A,i-1,j,Checked)==0 && Check(A,i,j+1,Checked)==0 && Check(A,i+1,j,Checked)==0 && Check(A,i,j-1,Checked)==0)
                {
                    base[k]=counter;
                    counter=0;
                    k++;
                    begin=0;
                }
            }
        }
    }
}

for(i=0;i<k;i++)
{
    printf("\nNumber of bases: %d\n",base[i]);
    printf("Most up-left base coords: <%d, %d> \n",lines[i],cols[i]);
}
return 0;
}

谢谢，波尔布

Answer 1

一种方式，愚蠢的伪代码:

int count_connected(set* traversed, element starting_element):
{
    int count = 0
    if set_insert(traversed, starting_element):
    {
        stack* to_process = stack_create()
        stack_push(to_process, starting_element)

        while not stack_empty(to_process):
        {
            element current_element = to_process.pop()
            for each adj_element to current_element:
            {
                if set_insert(traversed, adj_element):
                {
                    ++count
                    stack_push(to_process, adj_element)
                }
            }
        }
        stack_destroy(to_process)
    }
    return count
}

set_insert 在尝试插入副本时会返回 false。

针对您的情况对这个基本伪代码进行一些修改:element 将是矩阵中的一个位置(一种点/位置类型的 struct 或两个单独的整数)。

for each adj_element 将遍历值为 1 的相邻位置(就像您当前的代码现在检查左侧、上方、下方和右侧的条目有边界检查)。为避免大量代码，您可以在由相邻位置组成的堆栈上构建一个包含 4 个位置的数组，遍历它们，检查它们是否在边界内，以及它们是否不在 traversed 中设置。

您的遍历 集可以是一个相同大小的矩阵，被视为一个 bool 值矩阵，初始化为 0 (false) 用于常数时间集插入。或者你也可以将你的普通矩阵变成一个 structs 的矩阵，它存储一个 traversed 标志。如果您使用非常大的矩阵并且经常访问此标志(热)，那么这种交错代表往往会更有效率。如果不总是需要减少内存需求和可能的对齐开销，将它分开可能很有用。您还可以使用按位逻辑将它们全部组合在一起，其中矩阵条目存储 1/0 值以及是否已将其全部遍历为一个整数类型。

实现上述函数后，您可以通过从左上角到右下角遍历 1 条目的矩阵的循环来调用它。由于我们在调用中保持此 traversed 设置，因此对于已经遍历的矩阵条目，它将返回 0。返回非零的那些只会对左上角附近的区域这样做，因为我们正在从左上角到右下角遍历矩阵调用此 count_connected 函数。

例如，当我们调用位置 0,0 的函数作为 starting_element 时，我们最终使用堆栈和集合以深度优先的方式遍历该区域:

{*, *, *, 0, 1}
{0, 0, *, 0, 1}
{0, *, *, 0, 0}
{0, 0, 0, 0, 0}

函数返回 6，您可以将其与左上角坐标 0,0 一起打印出来。当您下次为 1,0 调用它时，它将返回 0，您可以跳过它。

如果你想允许以任意顺序调用函数并仍然返回左上角的元素，你可以跟踪函数中的元素位置并返回左上角的那个(最小值) y 和 x)。请注意，top-left 会变得有点模棱两可，比如:

{0, 0, 1, 0, 1}
{0, 0, 1, 0, 1}
{1, 1, 1, 0, 0}
{0, 0, 0, 0, 0}

在这种情况下，我假设您需要 2,0 以及您将通过上述方法获得的计数。如果你想要一个左上角(如边界框角)，如果你在元素中输出 min(x) 和 min(y) ，第二种方法将起作用您遍历的位置，在这种情况下您将获得 0,0。

剩下的就交给你了。