Given a binary matrix of size 10x10, where 0 represents water and 1 represents land, and connected ones form an island, count the total number of islands (using queue data structure) in c.

 

Given a binary matrix of size 10x10, where 0 represents water and 1 represents land, and connected ones form an island, count the total number of islands (using queue data structure) in c.

CODE:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
int M=10;
int N=10;

int row[] = { -1, -1, -1, 0, 1, 0, 1, 1 };
int col[] = { -1, 1, 0, -1, -1, 1, 0, 1 };
struct Queue {
    int front, rear, size;
    unsigned capacity;
    int* array;
};
struct Queue* createQueue(unsigned capacity)
{
    struct Queue* queue = (struct Queue*)malloc(
        sizeof(struct Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->rear = capacity - 1;
    queue->array = (int*)malloc(
        queue->capacity * sizeof(int));
    return queue;
}

int isFull(struct Queue* queue)
{
    return (queue->size == queue->capacity);
}

int isEmpty(struct Queue* queue)
{
    return (queue->size == 0);
}

void enqueue(struct Queue* queue, int item)
{
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1)
                  % queue->capacity;
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
}

int dequeue(struct Queue* queue)
{
    if (isEmpty(queue))
        return INT_MIN;
    int item = queue->array[queue->front];
    queue->front = (queue->front + 1)
                   % queue->capacity;
    queue->size = queue->size - 1;
    return item;
}

int front(struct Queue* queue)
{
    if (isEmpty(queue))
        return INT_MIN;
    return queue->array[queue->front];
}


int rear(struct Queue* queue)
{
    if (isEmpty(queue))
        return INT_MIN;
    return queue->array[queue->rear];
}
bool isSafe(int a[M][N], int x, int y, bool visited[M][N])
{
    return (x >= 0) && (x < M) && (y >= 0) && (y < N) && (a[x][y] && !visited[x][y]);
}

void BFS(int a[M][N], bool visited[M][N], int i, int j)
{
    struct Queue* q1 = createQueue(1000);
    struct Queue* q2 = createQueue(1000);
     enqueue(q1,i);
     enqueue(q2,j);
     visited[i][j] = true;
    while (!isEmpty(q1) && !isEmpty(q2))
    {
        int x = front(q1);
        int y = front(q2);
        dequeue(q1);
        dequeue(q2);
        for (int k = 0; k < 8; k++)
        {
            if (isSafe(a, x + row[k], y + col[k], visited))
            {

                visited[x + row[k]][y + col[k]] = 1;
                enqueue(q1,x+row[k]);
                enqueue(q2,y+col[k]);
            }
        }
    }
}

int main()
{
    int a[M][N];
    for(int i=0;i<M;i++)
    {
              for(int j=0;j<N;j++)
                    scanf("%d",&a[i][j]);
    }
    bool visited[M][N];
    memset(visited, 0, sizeof(visited));
    int island = 0;
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (a[i][j]==1 && visited[i][j] == 0)
            {
                BFS(a,visited, i, j);
                island++;
            }
        }
    }

    printf("%d",island);

    return 0;
}

INPUT:

1 0 1 0 0 0 1 1 1 1

0 0 1 0 1 0 1 0 0 0

1 1 1 1 0 0 1 0 0 0

1 0 0 1 0 1 0 0 0 0

1 1 1 1 0 0 0 1 1 1 

0 1 0 1 0 0 1 1 1 1

0 0 0 0 0 1 1 1 0 0

0 0 0 1 0 0 1 1 1 0

1 0 1 0 1 0 0 1 0 0

0 0 0 0 1 1 1 0 0 0

OUTPUT:

5