Monday, October 29, 2018

Explode the Active Bombs

Given a matrix of dimension M*N, where each cell in the matrix can have values 0, 1 or 2 which has the following meaning:

0: Empty cell
1: Cells have bombs, not activated yet.
2: Cells have activated bombs

And you have a trigger. After pressing the trigger all activated bomb at index [i,j] will explode in one second and will activate other bombs at indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right), which
will inturn explode in the next second and this continues. So we have to determine what is the time taken for all the bombs to explode, once the trigger is pressed. If it is impossible to explode every bomb, then simply return -1.

Sample Input : 2 X 2

2 1
1 0

Output: 2

Sample Input: 3 X 3

2 1 1
0 0 0
2 0 1

Output: -1

Sample Input:10 X 10

2 2 2 2 2 2 2 2 2 0
2 2 2 2 2 2 2 2 2 0
2 2 2 2 2 2 2 2 2 0
2 2 2 2 2 2 2 2 2 0
2 2 2 2 2 2 2 2 2 0
1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1
2 2 2 2 2 2 2 2 2 2
1 1 0 0 1 1 0 0 1 1
1 1 1 1 0 0 1 1 1 1

Output: 5

#include<stdio.h>
int explode(int a[][100], int n)
{
 int count = 0;
 int c;
 do {
     c = 0;
  for(int i=0; i<n; i++) {
   for(int j=0; j<n; j++) {
    if(a[i][j] == 2) {
     if(i>0 && a[i-1][j]==1) {
      a[i-1][j]=3;
      c++;
     }
     if(j>0 && a[i][j-1]==1) {
      a[i][j-1]=3;
      c++;
     }
     if(i<n-1 && a[i+1][j]==1) {
      a[i+1][j]=3;
      c++;
     }
     if(j<n-1 && a[i][j+1]==1) {
      a[i][j+1]=3;
      c++;
     }
    }
   }
  }
  for(int i=0; i<n; i++) {
      for(int j=0; j<n; j++) {
          if(a[i][j]==3)
              a[i][j]=2;
      }
  }
  count++;
 }while(c!=0);
 for(int i=0; i<n; i++) {
  for(int j=0; j<n; j++) {
   if(a[i][j] == 1)
    return -1;
  }
 }
 return count;
}

main()
{
 int n;
 int a[100][100];
 printf("Enter the size of the matrix: ");
 scanf("%d", &n);
 printf("Enter the matrix\n");
 for(int i=0; i<n; i++) {
  for(int j=0; j<n; j++) {
   scanf("%d", &a[i][j]);
  }
 }
 int ex = explode(a, n);
 printf("%d", ex);
 return 0;
}

No comments:

Post a Comment