时间戳

首页 > 解决方案 > 无法执行 Connected Object/ Island 程序

c - 无法执行 Connected Object/ Island 程序

问题描述

我编写了一个程序来识别二维整数矩阵中的岛屿。一个岛是 1 的集合，以这样的方式放置，每个 1 在周围的 8 个单元中至少与另一个 1 相邻。该程序适用于任何数组，除非相关的 1 在最后一行，并且对周围 1 的搜索超出了数组的最后一行。

这是我的代码

#include<stdio.h>
#include<stdlib.h>
void objectCount(int **arr, int row, int col, int i, int j)
{
    *(*(arr+i)+j) = -1; //Mark as visited
    int p,q;
    //Search for surrounding 8 cells
    for(p=i-1;p<=i+1;p++)
        for(q=j-1;q<=j+1;q++)
        {
            printf("\n\tTesting position %d,%d",p+1,q+1);
            //Condition to ensure search is within array boundaries, excluding the visited cell
            if((p!=i||q!=j) && !(p<0||q<0) && arr[p][q]==1 && (p<row && q<col))
            {
                printf("\n\t\tGoing to mark %d,%d",p+1,q+1);
                objectCount(arr,row,col,p,q); //Recursively call the function from the newly identified cell with 1
                printf("\n\t\tMarking %d,%d",p+1,q+1);
            }
            printf("\tTested position %d,%d",p+1,q+1);
        }
}
int islands(int **arr, int m, int n)
{
    int count=0,i,j;
    //Go through all the elements in the array
    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
            if(*(*(arr+i)+j)==1)
            {
                count++;
                printf("\nGroup spotted at %d,%d",i+1,j+1);
                objectCount(arr,m,n,i,j); //To mark the entire island with -1
            }
    return count;
}
void main()
{
    int m,n,i,j;
    printf("Enter number of rows:\n");
    scanf("%d",&m);
    printf("Enter number of columns:\n");
    scanf("%d",&n);
    int **a = malloc((m+1)*sizeof(int *));
    printf("Enter the matrix:\n");
    for(i=0;i<m;i++)
    {
        *(a+i) = malloc(n*sizeof(int));
        for(j=0;j<n;j++)
            scanf("%d",(*(a+i)+j));
    }
    printf("Number of connected objects = %d",islands(a,m,n));
}

这是我得到的输出

Enter number of rows:
3
Enter number of columns:
3
Enter the matrix:
1 1 0
0 0 0
1 0 1

Group spotted at 1,1
        Testing position 0,0    Tested position 0,0
        Testing position 0,1    Tested position 0,1
        Testing position 0,2    Tested position 0,2
        Testing position 1,0    Tested position 1,0
        Testing position 1,1    Tested position 1,1
        Testing position 1,2
                Going to mark 1,2
        Testing position 0,1    Tested position 0,1
        Testing position 0,2    Tested position 0,2
        Testing position 0,3    Tested position 0,3
        Testing position 1,1    Tested position 1,1
        Testing position 1,2    Tested position 1,2
        Testing position 1,3    Tested position 1,3
        Testing position 2,1    Tested position 2,1
        Testing position 2,2    Tested position 2,2
        Testing position 2,3    Tested position 2,3
                Marking 1,2     Tested position 1,2
        Testing position 2,0    Tested position 2,0
        Testing position 2,1    Tested position 2,1
        Testing position 2,2    Tested position 2,2
Group spotted at 3,1
        Testing position 2,0    Tested position 2,0
        Testing position 2,1    Tested position 2,1
        Testing position 2,2    Tested position 2,2
        Testing position 3,0    Tested position 3,0
        Testing position 3,1    Tested position 3,1
        Testing position 3,2    Tested position 3,2
        Testing position 4,0    Tested position 4,0
        Testing position 4,1
--------------------------------
Process exited after 26.35 seconds with return value 3221225477
Press any key to continue . . .

对于不同但相似的输入，输出应该是这样的

Enter number of rows: 
3
Enter number of columns: 
4 
Enter the matrix: 
1 1 0 0
0 0 0 1
1 1 0 1
Number of connected objects = 3

刚刚添加了“测试位置”和“标记”行以查看错误发生的位置。不知何故，程序在处理最后一行时卡在了 if 条件。任何想法如何找到问题并解决它。

我已经在 geeksforgeeks 等各种网站上看到过其他示例，但我想知道为什么该程序无法运行。

标签： c

解决方案

由于短路，订单很重要。如果你有一个 if 语句，比如

if(p<row && q<col)

如果p<row为假，它不会费心评估q<col，因为无论结果如何，它都不可能使整个表达式为真。如果if语句中有任何表达式以某种方式改变变量，请务必记住这一点。

但是，如果p<row为真，它将继续并检查q<col.

因此，通过在if or are out of bounds(p<row && q<col)的检查之前放置，它不会打扰。因此，像这样更改您的声明，您将避免任何进一步的超出范围的问题。arr[p][q]==1pqif

if((p!=i||q!=j) && p>=0 && q>=0 && p<row && q<col && arr[p][q]==1)

推荐阅读