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.

#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( "%sn", 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("%sn",s[i]);
    //system("pause");
    return 0;
}

coding problems solutions