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