Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Trying to find number of 1s groups in a given 2-dimensional array

I have written a code with recursive technique, but the program shows segmentation fault error. Did I Make any algorithm fault or its just a mistake in my code??

QUESTION:

There are R*C cells in a matrix where R is the number of rows and C is the number of cells in each row. Each cell may or may not have a fruit in it. The presence of a fruit is indicated by 1 and the absence of a fruit in a cell is indicated by 0. The fruits can be of different types and all the fruits belonging to the same type are arranged in adjacent cells (there are eight adjacent cells: top-left, top, top-right, left, right, bottom-left, bottom, bottom-right). The program must print the number of groups of fruits in the matrix.

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

Boundary Condition(s):
2 <= R, C <= 50

Input:
3 5
1 0 0 0 1
0 1 0 1 1
1 0 0 0 1
 
Output:
2
 
Explanation:
The first group is indicated by the letter F, 
F 0 0 0 1
0 F 0 1 1
F 0 0 0 1
The second group is indicated by the letter S,
1 0 0 0 S
0 1 0 S S
1 0 0 0 S

Input:
5 6
1 0 0 0 1 0 
0 0 1 1 1 0
1 0 0 0 1 0
0 0 0 0 0 0
1 1 0 1 1 1
 
Output:
5

A 1 must be at least adjacent of one 1 of the group to be considered as a member of the group.

My solution:

#include<stdio.h>
#include<stdlib.h>

int R, C, rtnval = 1;

int checkBoundary(int i, int j)
{
    return (i>-1 && j>-1 && i<R && j<C);
}

void checkGroup(int arr[R][C],int i, int j)
{
    if(arr[i][j]==1)
    {
        arr[i][j] = 0;
        //top
        if((checkBoundary(i-1,j)!=0) && arr[i-1][j]==1)
        {
            checkGroup(arr,i-1,j);
            //return;
        }
        //top-left
        if((checkBoundary(i-1,j-1)!=0) && arr[i-1][j-1]==1)
        {
            //arr[i-1
            checkGroup(arr,i-1,j-1);
            //return;
        }
        //top-right
        if((checkBoundary(i-1,j+1)!=0) && arr[i-1][j+1]==1)
        {
            //arr[i-1
            checkGroup(arr,i-1,j+1);
            //return;
        }
        //bottom
        if((checkBoundary(i+1,j)!=0) && arr[i+1][j]==1)
        {
            //arr[i+1
            checkGroup(arr,i+1,j);
            //return;
        }
        //bottom-left
        if((checkBoundary(i+1,j-1)!=0) && arr[i+1][j-1]==1)
        {
            checkGroup(arr,i+1,j-1);
        }
        //bottom-right
        if((checkBoundary(i+1,j+1)!=0) && arr[i+1][j+1]==1)
        {
            checkGroup(arr,i+1,j+1);
        }
        //left
        if((checkBoundary(i,j-1)!=0) && arr[i][j-1]==1)
        {
            checkGroup(arr,i,j-1);
        }
        //right
        if((checkBoundary(i,j+1)!=0) && arr[i][j+1]==1)
        {
            checkGroup(arr,i,j+1);
        }
    }
}


int main()
{
    scanf("%d%d",&R,&C);
    int arr[R][C];
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++)
        {
            scanf("%d",&arr[i][j]);
        }
    }
    int group = 0;
    for(int i=0;i<R;i++)
    {
        for(int j=0;j<C;j++)
        {
            if(arr[i][j]==1)
            {
                checkGroup(arr,i,j);
                group++;
            }
        }
    }
    printf("%d",group);
}
 

I have tried to follow all the leads to find any 1’s and make them 0 so that they cant be mistook for other adjacent 1s.

>Solution :

To begin with, you need to verify that checkBoundary(i, j) returns true before checking if arr[i][j] == 1 (and before attempting to access arr in general).

The same goes for each one of your internal ‘if’ statements, for example:

if(arr[i-1][j]==1 && (checkBoundary(i-1,j)!=0))

The checkBoundary call must be executed before accessing arr, not after.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading