Given a mtarix of size MxN, filled with 0s and 1s, representing 0 as black and 1 as white. find the number of shapes in it. The shape is defined as connected components of whites such that 2 whites of the matrix belong to the same shape if there is a path from one to the other over whites, where a path consist of successive points with coordinates (i,j) and (k,l) such that |i − k| ≤ 1 and |j − l| ≤ 1. Even single white cell without any neighboring white cells,  is shape.

For example given below figure:

Find shape in matrix

input 1:                           input 2:

0    1     0                      1    1    1

1    0     0                      1    0    0

1    0     1                      1   0     0

Answer: 2                         1    0    0    Answer:  1

Code:

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
 
#define ROW 3 
#define COL 3
 
#define NROW 4

void visit(int M[][COL], bool v[][COL] ,int i, int j){
      
         if(M[i][j] == 1){
            v[i][j] = true;
            if(j>0 && i< ROW){
                visit(M,v,i+1,j-1); // go South-West
            }
            if(i<ROW){
                visit(M,v,i+1,j); // go South
                if(j < COL)
                    visit(M,v,i+1,j+1); // go South-East
            }
            if(j<COL)
                visit(M,v,i,j+1); // go East
        }
}

int main()
{
    int M[][COL]= { 
        {0, 1, 0},
        {1, 0, 0},
        {1, 0, 1},
    };


    bool mvisited[ROW][COL];
    memset(mvisited,0,sizeof(M));

    int i,j;
    int count=0;

    for(i=0; i<ROW ; i++) {
            for(j=0; j<COL; j++){                
                if(M[i][j] == 1 && !mvisited[i][j]){
                    count++;
                    visit(M,mvisited,i,j);
                }
            }
        }

    printf("Number of shape: %d\n", count);
    count=0;

    int N[][COL]= {
     {1,1,1},
     {1,0,0},
     {1,0,0},
     {1,0,0},
    };

    bool nvisited[NROW][COL];
    memset(nvisited,0,sizeof(N));

    for(i=0; i<NROW ; i++) {
            for(j=0; j<COL; j++){                
                if(N[i][j] == 1 && !nvisited[i][j]){
                    count++;
                    visit(N,nvisited,i,j);
                }
            }
        }

    printf("Number of shape: %d\n", count);
    return 0;
}



Related Contents to follow