c - 使用 DFS 计算连接 block 的结果错误

Question

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

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

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

这是actual code.

这是主要部分，我删除了随机化函数，只是放置了一个程序遇到问题的数组。

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 上递归。

这种错误可能会导致内存损坏(因为您最终写入了无意的位置)，这几乎可能导致任何事情发生:-)。

如果您仔细检查此类不匹配情况，修复发现的任何不匹配情况，然后重试，会发生什么情况？