HackerEarth Connected Horses problem solution

In this HackerEarth Connected Horses problem solution You all must be familiar with the chess-board having 8 * 8 squares of alternate black and white cells. Well, here we have for you a similar N * M size board with similar arrangement of black and white cells.

A few of these cells have Horses placed over them. Each horse is unique. Now these horses are not the usual horses which could jump to any of the 8 positions they usually jump in. They can move only if there is another horse on one of the 8-positions that it can go to usually and then both the horses will swap their positions. This swapping can happen infinitely times.

A photographer was assigned to take a picture of all the different ways that the horses occupy the board! Given the state of the board, calculate answer. Since this answer may be quite large, calculate in modulo 10^9 7.

HackerEarth Connected Horses problem solution.

#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int> > moves(8);
int n,m;
long long MOD=1e9+7;

vector<long long> fact(1000001);

int a[1005][1005]={{0}};

int bfs(int x,int y)
 {
 int c=0;
    a[x][y]=2;
    queue<pair<int,int> > q;
    q.push(make_pair(x,y));
    while(q.size())
     {c++;
        pair<int,int> node=q.front();
        q.pop();
        x=node.first;
        y=node.second;
        for(int i=0;i<8;i++)
        {
        if(x+moves[i].first>=1 && x+moves[i].first<=n && y+moves[i].second>=1 && y+moves[i].second<=m &&a[x+moves[i].first][y+moves[i].second]==1)
          {
            a[x+moves[i].first][y+moves[i].second]=2;
            q.push(make_pair(x+moves[i].first,y+moves[i].second));
          }
      }
        
        
     }
     return fact[c];
 }

int main()
{
        
    moves[0]=make_pair(-1,-2);
    moves[1]=make_pair(-1,2);
    moves[2]=make_pair(1,-2);
    moves[3]=make_pair(1,2);
    
    moves[4]=make_pair(-2,-1);
    moves[5]=make_pair(-2,1);
    moves[6]=make_pair(2,-1);
    moves[7]=make_pair(2,1);
    
    fact[0]=1;
    for(int i=1;i<=1000000;i++)
     fact[i]=(i*fact[i-1])%MOD;
    
    //freopen("in09.txt","r",stdin);
    //freopen("out09.txt","w",stdout);

    int t,q,i,j,x,y;
    cin>>t;
    while(t--)
     {
        cin>>n>>m>>q;
        while(q--)
         {
            cin>>x>>y;
            a[x][y]=1;
         }
         long long ans=1;
        for(int i=1;i<=n;i++)
         {
            for(int j=1;j<=m;j++)
             {
                if(a[i][j]==1)
                  ans=(ans*bfs(i,j))%MOD;
             }
         }
        cout<<ans<<endl;
        for(int i=1;i<=n;i++)
         {
            for(int j=1;j<=m;j++)
             {
                a[i][j]=0;
             }
         }
     }
}

Second solution

#include<bits/stdc++.h>
 
 
using namespace std;
 
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define elif else if
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define gc getchar_unlocked


const int LIM = 1000005;
long long  fact[LIM];
ll mod= 1e9 + 7;
int mat[1000][1000];
int n,m;
void calc_fac()
{
  fact[0] = 1;
  for (int i = 1; i <= 1000000; i++)
    fact[i] = (i * fact[i-1]) % mod;
}

void dfs(int x,int y, int &tmp)
{
  if(x<0 || x>n-1 || y<0 || y>m-1 || mat[x][y]!=1)return;
  tmp++;
  mat[x][y]=2;
  dfs(x+2,y+1,tmp);
  dfs(x+1,y+2,tmp);
  dfs(x-2,y+1,tmp);
  dfs(x-1,y+2,tmp);
  dfs(x-2,y-1,tmp);
  dfs(x-1,y-2,tmp);
  dfs(x+2,y-1,tmp);
  dfs(x+1,y-2,tmp);
  return;
}
int main()
{
  calc_fac();
  int t;
  cin>>t;
  assert(1<=t && t<=10);
  while(t--)
  {
    int q,i,j;
    ll ans=1;
    memset(mat,0,sizeof(mat));
    cin>>n>>m>>q;
    assert(1<=n && n<=1000);
    assert(1<=m && m<=1000);
    assert(1<=q && q<=n*m);
    while(q--)
    {
      cin>>i>>j;
      assert(1<=i && i<=n);
      assert(1<=j && j<=m);
      i--;
      j--;
      mat[i][j]=1;
    }
    for(i=0;i<n;i++)
    {
      for(j=0;j<m;j++)
      {
        if(mat[i][j]==1)
        {
           int temp=0;
           dfs(i,j,temp);
           ans= (ans*fact[temp])%mod;
        }
      }
    }
    cout<<ans<<"n";
  }
  return 0;
}

HackerEarth Connected Horses problem solution.

Second solution

Leave a Reply