There is battlefield where some different types of aliens are fighting to each other. The battlefield exists some where on different planet. A scientist is able to watch the ongoing war from the earth. The scientist desire to categorize the war in terms of fighting group. He wants to calculate the largest fighting group. A group is defined as below.

  • Each alien is consider in a group if it is connected via left,right,up,down.

find-the-number-of-fighting-groups

Aliens on the matrix

Consider the battlefield as 2D matrix of size NxN, where every cell is filled with either 0 or one. one represents the alien while 0 means empty space. find the number of fighting groups.

Input:

0 1 1 0 0 0 0 1
0 1 1 0 1 0 0 1
1 0 1 0 1 0 1 1
0 0 0 0 1 1 1 0
1 0 1 0 0 0 0 1
0 1 1 1 1 1 0 1
0 1 0 1 1 0 0 0
0 0 0 0 1 1 1 0

output:

There are 6 fighting groups

Solution using dfs

#include <stdio.h>

const int N=8;

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

int dfs (int i, int j)
{
    int aliens = 0;
  
    if (mat[i][j] == 1)
    {
      aliens++;
      // make i,j cell visited 
      mat[i][j] = 0;

      if (j + 1 < N) // go right
	    aliens += dfs (i, j + 1);

      if (i + 1 < N)  // go down
	    aliens += dfs (i + 1, j);

      if (j - 1 >= 0) // go left
	    aliens += dfs (i, j - 1);

      if (i - 1 >= 0) // go up
	    aliens += dfs (i - 1, j);
     }
  
   return aliens;
}

int main (void)
{
      int no_of_aliens = 0;
      int i,j=0;
      int groups =0;

        for (i = 0; i < N; i++)
	{
	    for (j = 0; j < N; j++)
	    {
	        no_of_aliens = dfs (i, j);
                if( no_of_aliens > 0)
		 groups++;
	    }
	}

      printf ("There are %d fighting groups\n", groups);
  return 0;
}

 




Related Contents to follow