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:

output:

Solution using dfs