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。

下面是我 post 到目前为止的源代码。它只为某些矩阵打印正确答案，因为我的代码只检查 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;
}

谢谢，Polb

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 尝试插入副本时会 return false。

针对您的情况对这个基本伪代码进行一些修改：element 将是矩阵中的一个位置（point/position 类 struct 或两个单独的整数）。

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

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

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

例如，当我们将位置 0,0 的函数调用为 starting_element 时，我们最终使用堆栈以深度优先的方式遍历该区域并设置：

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

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

如果你想允许以任意顺序调用函数并且仍然 return 左上角元素，你可以跟踪函数中的元素位置和 return左上角的一个（最小值 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.

剩下的交给你了

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

C-listing the biggest vicinity of same numbers in a matrix

c

iteration

matrix