HackerEarth Game problem solution

YASH PAL, 31 July 202416 February 2026

In this HackerEarth Game problem solution You are playing a game in which you have a rectangular grid of n*n cells. Each cell is either empty or has a firework. Empty cells are marked with “.”, cells with firework are marked with “*” . Two cells are said to be adjacent if they share a side.

If firework in any cell explodes it destroys itself and the empty cells connected to it. Two cells are connected if there is a path of empty adjacent cells between them.

You have to find the number of cells that will be destroyed if the fireworks are triggered independently.

HackerEarth Game problem solution

HackerEarth Game problem solution.

#include <bits/stdc++.h>

using namespace std;

int X[] = {0, 0, 1, -1};
int Y[] = {-1, 1, 0, 0};

string s[1005];
int vis[1005][1005];
int cnt[1000005];
int mrk[1000005];

bool valid(int x, int y, int n, int m)
{
    return (x >= 0 && y >= 0 && x < n && y < n && s[x][y] == '.');
}

void dfs(int x, int y, int n, int m, int p)
{
    if (vis[x][y] != -1)
        return;
    vis[x][y] = p;
    cnt[p]++;
    int i, tx, ty;
    for (i = 0; i < 4; ++i) {
        tx = x + X[i];
        ty = y + Y[i];
        if (valid(tx, ty, n, m))
            dfs(tx, ty, n, m, p);
    }
}

int main()
{
    memset(vis, -1, sizeof(vis));

    int n, m, i, j, k, tx, ty;
    cin >> n;
    for (i = 0; i < n; ++i)
        cin >> s[i];
    m = s[0].size();
    for (i = 0; i < n; ++i) {
        for (j = 0; j < m; ++j) {
            if (s[i][j] == '*')
                continue;
            dfs(i, j, n, m, i*m+j);
        }
    }
    long long int ans = 0;
    for (i = 0; i < n; ++i) {
        for (j = 0; j < m; ++j) {
            if (s[i][j] == '.')
                continue;
            ans++;
            for (k = 0; k < 4; ++k) {
                tx = i + X[k];
                ty = j + Y[k];
                if (valid(tx, ty, n, m) && !mrk[vis[tx][ty]])
                    ans += cnt[vis[tx][ty]], mrk[vis[tx][ty]] = 1;
            }
            for (k = 0; k < 4; ++k) {
                tx = i + X[k];
                ty = j + Y[k];
                if (valid(tx, ty, n, m))
                    mrk[vis[tx][ty]] = 0;
            }
        }
    }
    cout  << ans << endl;
    return 0;
}

Second solution

#include<bits/stdc++.h>
#define ll long long
using namespace std;
char mat[1005][1005];
bool vis[1005][1005];
int ind[1005][1005],n;
ll ans,val[1000005],idx;
void dfs(int x,int y)
{
    if(vis[x][y])return ;
        vis[x][y]=1;
        if(y+1<n && mat[x][y+1]=='.' && !vis[x][y+1]){ans++;dfs(x,y+1);}
        if(y-1>=0 && mat[x][y-1]=='.' && !vis[x][y-1]){ans++;dfs(x,y-1);}
        if(x+1<n && mat[x+1][y]=='.' && !vis[x+1][y]){ans++;dfs(x+1,y);}
        if(x-1>=0 && mat[x-1][y]=='.' && !vis[x-1][y]){ans++;dfs(x-1,y);}
    ind[x][y]=idx;
    val[idx]=ans;
        return;
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>mat[i][j];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(mat[i][j]=='.' && !vis[i][j])
            {
                ans=1;
                dfs(i,j);
                idx++;
            }
        }
    }
    ll tot=0;
    for(int x=0;x<n;x++)
        {
                for(int y=0;y<n;y++)
                {
                        if(mat[x][y]=='*')
                        {
                tot++;
                set<int>s;
                if(y+1<n && mat[x][y+1]=='.'){s.insert(ind[x][y+1]);}
                    if(y-1>=0 && mat[x][y-1]=='.'){s.insert(ind[x][y-1]);}
                    if(x+1<n && mat[x+1][y]=='.'){s.insert(ind[x+1][y]);}
                    if(x-1>=0 && mat[x-1][y]=='.'){s.insert(ind[x-1][y]);}
                set<int>:: iterator it;
                for(it=s.begin();it!=s.end();it++)
                    tot+=val[*it];
                        }
            }
    }
    cout<<tot<<"n";
    return 0;
}

coding problems solutions HackerEarth HackerEarth

Leave a Reply