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

Friday, October 26, 2018

How will you trap rain water?

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.



Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Input: [3, 0, 0, 2, 0, 4]
Output: 10

#include<stdio.h>
calculate(int a[], int n)
{
 int f = a[0];
 int fi = 0;
 int sum = 0;
 for(int i=0; i<n; i++) {
  int next = getNextGENumber(a, a[i], i, n);
  if(next != -1) {
   for(int j=i+1; j<next; j++) {
    sum += (a[i]-a[j]);
   }
   i = next - 1;
  } 
 }
 return sum;
}

int getNextGENumber(int a[], int value, int start, int n)
{
 for(int i=start+1; i<n; i++) {
  if(value <= a[i]) {
   return i;
  }
 }
 return -1;
}

main()
{
 int n;
 int a[1000];
 printf("Enter number of blocks: ");
 scanf("%d", &n);
 printf("Enter the blocks\n");
 for(int i=0; i<n && i<1000; i++) {
  scanf("%d", a+i);
 }
 printf("%d\n", calculate(a, n));
}