# Find the number of fighting groups using dfs

*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*.

*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:**

1 2 3 4 5 6 7 8 |
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: **

1 |
There are 6 fighting groups |

*Solution using dfs*

*Solution using dfs*

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#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; } |

## Leave a Reply