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