• • 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: ```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;
}```