Header Ad

HackerEarth Game of Cubes problem solution

In this HackerEarth Game of Cubes problem solution Alice and Bob are playing a game. In this game small cubes are placed over each other, forming a cuboid of length B, height L and breadth 1.
The special property in these cubes is that adjacent cubes always form a cluster.


HackerEarth Game of Cubes problem solution


HackerEarth Game of Cubes problem solution.

#include <algorithm>
#include <cstdio>
#include <vector>
#include<string.h>
using namespace std;

typedef pair<int,int> par;

#define MAXR 100
#define MAXS 100

int R, S;
char a[MAXR][MAXS+1];
char bio[MAXR][MAXS+1];

vector<par> nakupina;

void dfs( int r, int s ) {
if( r < 0 || r >= R ) return;
if( s < 0 || s >= S ) return;
if( a[r][s] == '.' ) return;
if( bio[r][s] ) return;
bio[r][s] = 1;
nakupina.push_back( par(r,s) );
dfs( r, s-1 );
dfs( r, s+1 );
dfs( r-1, s );
dfs( r+1, s );
}

void srusi() {
memset( bio, 0, sizeof bio );

for( int r = 0; r < R; ++r ) {
for( int s = 0; s < S; ++s ) {
if( a[r][s] == '.' || bio[r][s] ) continue;

nakupina.clear();
dfs( r, s );

vector<int> najniza( S, -1 );
for( vector<par>::iterator it = nakupina.begin(); it != nakupina.end(); ++it ) {
najniza[it->second] = max( najniza[it->second], it->first );
a[it->first][it->second] = '.';
}

int padni = R;
for( int i, j = 0; j < S; ++j ) {
if( najniza[j] == -1 ) continue;
for( i = najniza[j]+1; i < R && a[i][j] == '.'; ++i );
padni = min( padni, i-najniza[j]-1 );
}

for( vector<par>::iterator it = nakupina.begin(); it != nakupina.end(); ++it ) {
it->first += padni;
a[it->first][it->second] = 'x';
bio[it->first][it->second] = 1;
}
}
}
}

int main( void ) {
scanf( "%d%d", &R, &S );
for( int r = 0; r < R; ++r ) scanf( "%s", a[r] );

int N;
scanf( "%d", &N );
for( int i = 0; i < N; ++i ) {
int h;
scanf( "%d", &h );

int r = R-h;
if( i % 2 == 0 ) {
for( int s = 0; s < S; ++s )
if( a[r][s] == 'x' ) { a[r][s] = '.'; break; }
} else {
for( int s = S-1; s >= 0; --s )
if( a[r][s] == 'x' ) { a[r][s] = '.'; break; }
}

srusi();
}

for( int r = 0; r < R; ++r ) printf( "%s\n", a[r] );
return 0;
}

Second solution

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<cassert>
#include<set>
#include<queue>
#include<map>

using namespace std;

#define vi vector < int >
#define pb push_back
#define mp make_pair
#define ll long long
#define llu unsigned long long
#define MOD 1000000007
#define INF 2000000000
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define all(x) x.begin(),x.end()

int l,b;
int dirx[]={1,0,-1,0};
int diry[]={0,1,0,-1};
int vis[102][102];
char s[102][102];
vector < pair<int,int> > v;

void get(int x,int y)
{
if(x>=l || y>=b || x<0 || y<0)
return;

if(s[x][y]=='.' || vis[x][y])
return;

vis[x][y] = 1;
s[x][y] = '.';
v.pb(mp(x,y));
int i;
for(i=0;i<4;i++)
{
int nx = x + dirx[i];
int ny = y + diry[i];
get(nx,ny);
}
}

void move()
{
int i,j;

for(i=0;i<l;i++)
{
for(j=0;j<b;j++)
{
vis[i][j] = 0;
}
}

for(i=0;i<l;i++)
{
for(j=0;j<b;j++)
{
if(s[i][j] == 'x' && !vis[i][j])
{
v.clear();

get(i,j);

int x;


int shift = l;

for(x=0;x<v.size();x++)
{
int len = 0;
for(len = v[x].first + 1;len < l && s[len][v[x].second] == '.';len++);
shift = min(shift,len-v[x].first-1);
}

for(x=0;x<v.size();x++)
{
s[v[x].first+shift][v[x].second] = 'x';
vis[v[x].first+shift][v[x].second] = 1;
}
}
}
}
}

int main()
{
int i,j;
int n;
scanf("%d%d",&l,&b);
assert(1<=l && l<=100);
assert(1<=b && b<=100);
for(i=0;i<l;i++)
{
scanf("%s",s[i]);
for(j=0;j<b;j++)
{
assert(s[i][j]=='.' || s[i][j]=='x');
}
assert(s[i][j]==0);
}
scanf("%d",&n);
assert(1<=n && n<=100);
for(i=0;i<n;i++)
{
int h;
scanf("%d",&h);
assert(1<=h && h<=l);
if(i&1)
{
for(j=b-1;j>=0;j--)
{
if(s[l-h][j]=='x')
break;
}
}
else
{
for(j=0;j<b;j++)
{
if(s[l-h][j]=='x')
break;
}
}
if(j!=b)
s[l-h][j] = '.';
move();
}
for(i=0;i<l;i++)
printf("%s\n",s[i]);
//system("pause");
return 0;
}

Post a Comment

0 Comments