# HackerEarth Game problem solution

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.

`#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 longusing 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;}`