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;
}

1 comment:

  1. If you encounter an unfortunate streak of losses, the amount want to|you should|you have to} bet could exceed this limit, additionally inflicting you to dafabet not cowl your losses. The Brach’s candy corn gave the impression to be going for the same Russian-roulette effect, because the that} flavors have been jumbled and the colours weren’t an instantaneous giveaway. Inside Bets are these where you place chips directly on a quantity or a gaggle of them. Dozen – Similar to column bets but you cowl the primary 12 numbers, or the middle or final 12. As the researchers observe in the paper, "for the casino the information is generally good—minor adjustments will ameliorate the advantage of the physicist-gambler." For extra info, see the developer’s privateness coverage.

    ReplyDelete