Given a 2–d matrix , which has only 1’s and 0’s in it. Find the total number of connected sets in that matrix.

Explanation:

Connected set can be defined as group of cell(s) which has 1 mentioned on it and have at least one other cell in that set with which they share the neighbor relationship. A cell with 1 in it and no surrounding neighbor having 1 in it can be considered as a set with one cell in it. Neighbors can be defined as all the cells adjacent to the given cell in 8 possible directions ( i.e N , W , E , S , NE , NW , SE , SW direction ). A cell is not a neighbor of itself.

Input format :

First line of the input contains T , number of test-cases.

Then follow T testcases. Each testcase has given format.

N [ representing the dimension of the matrix N X N ].

Followed by N lines , with N numbers on each line.

Ouput format :

For each test case print one line ,  number of connected component it has.

Sample Input :

4

4

0 0 1 0

1 0 1 0

0 1 0 0

1 1 1 1

4

1 0 0 1

0 0 0 0

0 1 1 0

1 0 0 1

5

1 0 0 1 1

0 0 1 0 0

0 0 0 0 0

1 1 1 1 1

0 0 0 0 0

8

0 0 1 0 0 1 0 0

1 0 0 0 0 0 0 1

0 0 1 0 0 1 0 1

0 1 0 0 0 1 0 0

1 0 0 0 0 0 0 0

0 0 1 1 0 1 1 0

1 0 1 1 0 1 1 0

0 0 0 0 0 0 0 0

Sample output :

1

3

3

9

Constraint :

0 < T < 6 

0 < N < 1009 

=================WORKING CODE=================

#include<stdio.h>

int count_connected_set(int A[1015][1015],int i,int j,int n)

{

    A[i][j]=2;

    if(A[i-1][j-1]==1 && i>0 && j>0 && i<=n && j<=n )     //NW

        count_connected_set(A,i-1,j-1,n);

    if(A[i-1][j]==1 && i>0 && j>0 && i<=n && j<=n)       //N

        count_connected_set(A,i-1,j,n);

    if(A[i-1][j+1]==1 && i>0 && j>0 && i<=n && j<=n)//   //NE

        count_connected_set(A,i-1,j+1,n);

    if(A[i][j-1]==1 && i>0 && j>0 && i<=n && j<=n)       //W

        count_connected_set(A,i,j-1,n);

    if(A[i][j+1]==1 && i>0 && j>0 && i<=n && j<=n)       //E

        count_connected_set(A,i,j+1,n);

    if(A[i+1][j-1]==1 && i>0 && j>0 && i<=n && j<=n)     //SW

        count_connected_set(A,i+1,j-1,n);

    if(A[i+1][j]==1 && i>0 && j>0 && i<=n && j<=n)       //S

        count_connected_set(A,i+1,j,n);

    if(A[i+1][j+1]==1 && i>0 && j>0 && i<=n && j<=n)     //SE

        count_connected_set(A,i+1,j+1,n);

return 1;

}// end of count_connected_set()

int main()

{

    int i,j,t,k,n,A[1015][1015],count;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(i=1;i<=n;i++)

            for(j=1;j<=n;j++)

                scanf("%d",&A[i][j]); // geting input a test case;

        count =0;

        for(i=1;i<=n;i++)

        {

            for(j=1;j<=n;j++)

                if(A[i][j]==1)

                    if(count_connected_set(A,i,j,n))

                        count++;

        }// of for

        printf("%d\n",count);

    }// end of while

return 0;

}

Let me know your thoughts.

REVERSE a string and if any charecter is repeating then keep that one comes last

    INPUT           OUTPUT
    ABC             CBA
    ABBC            CBA
    NHHGFDGS        SGDFHN
    ABBCC           CBA

#include<stdio.h>
#include<string.h>
int main()
{
    char S[20],S1[20];
    int i,x,j,l,A[26]={0},count=0;
    gets(S);            // UPPER CASE ONLY
    l=strlen(S);
    for(i=0;i<l;i++)
    {
        x=S[i]-'A'+1;
        if(!A[x])
            count++;
        A[x]++;
    }
    S1[count]=NULL;
    for(j=l-1,i=0;count>i;)
    {
        x=S[j]-'A'+1;
        if(A[x]>0)
        {
            S1[i++]=S[j];
            A[x]=0;
        }
        j--;
    }
    printf("\n> %s",S1);
return 0;
}

WAP to find the position of a given word in a given text

WAP to find the position of a given word in a given text.
  INPUT  :
        Text : my name is kumar name
        Word : name
 OUTPUT :
         Position  : 3 17

#include<stdio.h>
#include<string.h>
int main()
{
    char S[100],W[20];
    int i,j,l,m,flage=0;
    printf("Enter Text : ");
    gets(S);
    printf("\nEnter Word : ");
    gets(W);
    l=strlen(S);
    m=strlen(W);
    for(i=0;i<l;i++)
    {
        if(S[i]==W[0])
        {
            for(j=1;j<m;j++)
            {
                if(S[i+j]!=W[j])
                    break ;
            }
            if(j==m)
            {
                if(!flage)
                    printf("\nPosition : ");
                flage =1;
                printf(" %d",i);
                //flage=
            }
        }
    }
    if(!flage)
        printf("\nNot found \n");
return 0;
}

Let me know your thoughts.

Which type of triangle is ?

Write a function that receives three integer inputs for the lengths of the sides of
a triangle and returns one of four values to determine the triangle type
(1=scalene, 2=isosceles, 3=equilateral, 4=error).

#include<stdio.h>
int which_triangle(int a,int b,int c)
{
    if( !(a&&b&&c&&(a+b)>c&&(a+c)>b&&(b+c)>a) )
        return 4;
    else if(a==b && a==c)
        return 3;
    else if(a==b || a==c || b==c)
        return 2;
    else
        return 1;
}

int main()
{
    int a,b,c,x;
    printf("enter 3 side length : ");
    scanf("%d %d %d",&a,&b,&c);
    x=which_triangle(a,b,c);
    switch(x){
    case 1:
        printf("\nScalene Triangle\n");
        break ;
    case 2:
        printf("\nIsoscalene Triangle\n");
        break ;
    case 3:
        printf("\nEquilateral Triangle\n");
        break ;
    case 4:
        printf("\nError\n");
        break ;
    }// end of switch
return 0;
}

Let me know your thoughts.

Find the number of substrings of a string that are palindromes

// INPUT : w3asd1dsaf
// OUTPUT
asd1dsa
sd1ds
d1d
total 3 palindrom in given string

#include<stdio.h>
#include<string.h>

int is_palindrom(char S[20],int f,int l)
{
    for(;f<=l;f++,l--)
    {
        if(S[f]!=S[l])
            return 0;
    }
return 1;
}
int main()
{
    char S[20];
    int i,l,j,k,count=0;
    gets(S);
    l=strlen(S);
    for(i=0;i<l;i++)
    {
        for(j=i+1;j<l;j++)
        {
            if(S[i]==S[j])
                if(is_palindrom(S,i,j))
                {
                    printf("\n");
                    count++;
                    for(k=i;k<=j;k++)
                        printf("%c",S[k]);
                }
        }
    }
    printf("\n\nTotal << %d >> no of palindrom in given string\n",count);
return 0;
}

Let me know your thoughts.

To copy the contents of an array A to contents of Array B without using loops and any standard string copy functions.

#include<stdio.h>
int Copy_Array(int A[],int B[], int n,int i)
{
    if(i==n)
        return 0;
    B[i]=A[i];
    Copy_Array(A,B,n,i+1);
return 0;
}

int main()
{
    int A[10],B[10],i,n;
    printf("Enter size : ");
    scanf("%d",&n);
    printf("Enter Array : ");
    for(i=0;i<n;i++)
        scanf("%d",&A[i]);
    printf("\nArray A : ");
    for(i=0;i<n;i++)
        printf("%d ",A[i]);
    Copy_Array(A,B,n,0);
    printf("\nArray B : ");
    for(i=0;i<n;i++)
        printf("%d ",B[i]);
return 0;
}

Let me know your thoughts.