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