HackerEarth We Are On Fire problem solution

In this HackerEarth We Are On Fire problem solution An intergallactic war is on. Aliens are throwing fire-balls at our planet and this fire is so deadly that whichever nation it hits, it will wipe out not only that nation, but also spreads to any other nation which lies adjacent to it.

Given an NxM map which has N x M cells. Each cell may have a country or else it may be the ocean. Fire cannot penetrate the ocean or go beyond the edges of the map (a wise man managed to bound the corners preventing fire from wrapping around the corners).

You will be given a initial state of the planet represented by an N x M grid consists of 0 or 1 representing ocean and nation respectively. Also there will be Q attacks of the fire-ball. After each query, you are to tell the number of nations still left unburnt.

HackerEarth We Are On Fire problem solution.

#include<bits/stdc++.h>
using namespace std;
int nodesLeft=0;
int n,m;
int a[1005][1005]={{0}};

//ZERO = EMPTY
//ONE = ALIVE
//TWO = BURNT

void burn(int x,int y)
 {
    a[x][y]=2;
    nodesLeft--;
    if(x+1<=n && a[x+1][y]==1)
      burn(x+1,y);
    if(x-1>=1 && a[x-1][y]==1)
      burn(x-1,y);
    if(y+1<=m && a[x][y+1]==1)
      burn(x,y+1);
    if(y-1>=0 && a[x][y-1]==1)
      burn(x,y-1);
    
 }


int main()
{
    int i,j,q,x,y;
    cin>>n>>m>>q;
    for(i=1;i<=n;i++)
     {
        for(j=1;j<=m;j++)
         {
            scanf("%d",&a[i][j]);
            nodesLeft+=a[i][j];
         }
     }
    
    while(q--)
     {
        scanf("%d%d",&x,&y);
        assert(x>=1 && x<=n && y>=1 && y<=m);
        if(a[x][y]==1)
            burn(x,y);
        printf("%dn",nodesLeft);
     }
    
    
}

Second solution

#include <bits/stdc++.h>
using namespace std ;
#define sc(x) scanf("%d",&x)
#define MAXN 1111
int N,M,Q,total;
bool maze[MAXN][MAXN] ;
int X[] = {-1,0,1,0} ;
int Y[] = {0,1,0,-1} ;

bool isvalid(int r,int c){
    return (r <= N && c <= M && r >= 1 && c >= 1) ;
}

void solve(int r,int c){
    if(!maze[r][c])
        return ;
    total -- ;
    maze[r][c] = 0 ;
    for(int i=0;i<4;i++){
        int nr,nc ;
        nr = r + X[i] ;
        nc = c + Y[i] ;
        if(isvalid(nr,nc)){
            solve(nr,nc) ;
        }
    }
}
int main(){
    sc(N) ; sc(M) ; sc(Q) ;
    assert(N <= 1000 && N >= 1) ;
    assert(M <= 1000 && M >= 1) ;
    assert(Q <= 1000000 && Q >= 1) ;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            sc(maze[i][j]) ;
            assert( maze[i][j] <= 1 && maze[i][j] >= 0 ) ;
            if(maze[i][j]) total ++ ;
        }
    }
    while(Q--){
        int x,y;
        sc(x) ; sc(y) ;
        assert(x <= N && x >= 1) ;
        assert(y <= M && y >= 1) ;
        solve(x,y) ;
        printf("%dn",total) ;
    }
    return 0 ;
}

coding problems solutions