使用我的 DFS 计算连接块的错误结果

Question

我有一个随机生成的 5 x 5 矩阵，由 1 和 0 组成，我应该找到 1 的块。

一个1本身就是一个方块，如果它从任何方向连接到另一个1，我的算法应该找到所有连接的1并将它们全部算作一个方块。

问题是我无法获得一致的结果，有时计数器甚至会达到 -1。

这是主要的，我已经删除了随机化函数，只是放置了一个程序有问题的数组。

struct parent {
    int row;
    int col;
}

int ar[5][5] = { 0,0,0,0,1,
                 1,0,0,0,1,
                 0,0,0,0,0,
                 0,0,0,0,0,
                 0,0,0,0,0 };
int countblock=0,num=0;
struct parent pos[30] = { 0 };
srand(time(NULL));
printf("      ---Find the connected blocks---     \n\n");
printf("Creating a random array:\n");
//random5x5(ar);
for (int row = 0, col; row < 5; row++)
{
    for (col = 0; col < 5; col++)
    {
        if (ar[row][col] == 1)
        {
            countblock++;
            ar[row][col] = -1;
            flag = 0;
            check(ar, row, col, pos, &num);
        }
        printf("%d ", ar[row][col]);  // Had problems with this loop not checking 1's
    }  //So I printed them to try to make sure
    printf("\n");
}
printf("\n\n Found the connected blocks! I see only %d of them.", countblock);
return 0;

而 DFS 函数应该标记它在任何方向上找到的 1

int flag=0; // declared in global

void check(int ar[5][5], int row, int col, struct parent pos[30],int *num){
if (col - 1 >= 0 && row - 1 >= 0)   //Checking Upper-left
{
    if (ar[row - 1][col - 1] == 1) {
        ar[row - 1][col - 1] = -1;
        (*num)+=1;
        pos[*num].row = row; pos[*num].col = col; //Store this position
        check(ar, row - 1, col - 1, pos, num);  //Jump to the found 1
    }
}
if (col - 1 >= 0)       //Checking Left
{
    if (ar[row][col - 1] == 1) {
        ar[row][col - 1] = -1;
        (*num)+=1;
        pos[*num].row = row; pos[*num].col = col;  //Store this position
        check(ar, row, col - 1, pos, num);  //Jump to the found 1
    }
}
if (col - 1 >= 0 && row + 1 <= 4)   //Checking Bottom-Left
{
    if (ar[row + 1][col - 1] == 1) {
        ar[row + 1][col - 1] = -1;
        (*num)+=1;
        pos[*num].row = row; pos[*num].col = col; //
        check(ar, row + 1, col - 1, pos, num); //
    }
}
if (row + 1 <= 4)       //Checking Bottom
{
    if (ar[row + 1][col] == 1) {
        ar[row + 1][col] = -1;
        (*num)+=1;
        pos[*num].row = row; pos[*num].col = col; //
        check(ar, row + 1, col, pos, num); //
    }
}
if (col + 1 <= 4 && row + 1 <= 4)   //Checking Bottom-Right
{
    if (ar[row + 1][col + 1] == 1) {
        ar[row + 1][col + 1] = -1;
        (*num)+=1;
        pos[*num].row = row; pos[*num].col = col; //
        check(ar, row + 1, col + 1, pos, num); //
    }
}
if (col + 1 <= 4)       //Checking Right
{
    if (ar[row][col + 1] == 1) {
        ar[row][col + 1] = -1;
        (*num)+=1;
        pos[*num].row = row; pos[*num].col = col; //
        check(ar, row, col + 1, pos, num); //
    }
}
if (col + 1 <= 4 && row - 1 >= 0)      //Checking Upper-Right
{
    if (ar[row - 1][col + 1] == 1) {
        ar[row - 1][col + 1] = -1;
        (*num)+=1;
        pos[*num].row = row; pos[*num].col = col; //
        check(ar, row - 1, col + 1, pos, num); //
    }
}
if (row - 1 >= 0)  //Checking Up
{
    if (ar[row - 1][col] == 1) {
        ar[row - 1][col] = -1;
        (*num)+=1;
        pos[*num].row = row; pos[*num].col = col; //
        check(ar, row - 1, col, pos, num); //
    }
}
if (*num == 0)  //There were no 1's around
    return;
else  //Reached the end of the path, call back
{
    flag++;
    if (flag >= 2) //On first call back the pos is still on parent call
        (*num)-=1;  // On second call it should go back
    check(ar, pos[*num].row, pos[*num].col, pos, num);
}

编辑：这是错误

flag++;
    if (flag >= 2) //On first call back the pos is still on parent call
        (*num)-=1;  // On second call it should go back
    check(ar, pos[*num].row, pos[*num].col, pos, num);

通过制作修复它

flag++;
    if (flag >= 2)
        (*num)-=1;
    if (*num == 0)
        return;
    check(ar, pos[*num].row, pos[*num].col, pos, num);

基本上 *num 会在 else 中变为零并调用错误的父位置。进行另一次检查使它起作用。

Answer 1

您所做的范围检查与您检查的邻居之间存在一些不匹配。例如（这不是唯一的）看这个：

if (row + 1 <= 4)       //Checking Bottom
{
    if (ar[row][col + 1] == 1) {
        ar[row][col + 1] = -1;
        (*num)+=1;
        pos[*num].row = row; pos[*num].col = col; //
        check(ar, row, col + 1, pos, num); //
    }
}

您检查 row+1 在范围内...但随后您递归 col+1。

这种错误会导致内存损坏（因为您最终写入了您不希望写入的位置），这几乎会导致任何事情发生:-)。

如果您仔细检查这种不匹配，修正您发现的任何问题，然后重试，会发生什么情况？

使用我的 DFS 计算连接块的错误结果

Wrong results on counting connected blocks with my DFS

c

matrix

depth-first-search

output