USACO (Complete Search) : Transformations

Problem Link : http://train.usaco.org/usacoprob2?a=SeMATkWVe9o&S=transform


/*
PROG: transform
LANG: C++
*/
#include <bits/stdc++.h>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 10000
#define CIN ios_base::sync_with_stdio(0)
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define loop(i,n) for(int i=0;i<n;i++)
#define TEST_CASE(t) for(int z=1;z<=t;z++)
#define PRINT_CASE printf("Case %d: ",z)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;

class Matrix
{

    char ara[11][11];
    int n;
public:
    void set_n(int x)
    {
        n=x;
    }
    int get_n()
    {
        return n;
    }

    friend istream& operator>>(istream & in, Matrix &xx);
    friend ostream& operator<<(ostream & in, Matrix &xx);

    bool operator==(Matrix xx)
    {
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
            {
                if(ara[i][j]!=xx.ara[i][j])
                    return false;
            }
        return 1;
    }

    friend Matrix Rotate_90(Matrix xx);
    friend Matrix Rotate_180(Matrix xx);
    friend Matrix Rotate_270(Matrix xx);
    friend Matrix Rotate_270(Matrix xx);
    friend Matrix Reflex(Matrix xx);
};

istream& operator>>(istream &in, Matrix &xx)
{
    for(int i=0; i<xx.n; i++)
        for(int j=0; j<xx.n; j++)
        {
            in>>xx.ara[i][j];
        }
    return in;
}

ostream& operator<<(ostream& in, Matrix &xx)
{
    for(int i=0; i<xx.n; i++,cout<<endl)
        for(int j=0; j<xx.n; j++)
        {
            in<<xx.ara[i][j]<<" ";
        }
    return in;
}

Matrix Rotate_90(Matrix xx)
{
    Matrix temp;
    temp.n=xx.n;
    for(int i=0; i<xx.n; i++)
        for(int j=0; j<xx.n; j++)
        {
            temp.ara[i][j]=xx.ara[xx.n-j-1][i];
        }
    return temp;
}

Matrix Rotate_180(Matrix xx)
{
    Matrix temp=Rotate_90(xx);
    Matrix temp1=Rotate_90(temp);
    return temp1;
}

Matrix Rotate_270(Matrix xx)
{
    Matrix temp=Rotate_90(xx);
    Matrix temp1=Rotate_180(temp);
    return temp1;
}

Matrix Reflex(Matrix xx)
{
    Matrix temp;
    temp.n=xx.n;
    for(int j=0; j<xx.n; j++)
        for(int i=xx.n-1,k=0; k<xx.n; k++,i--)
        {
            temp.ara[j][k]=xx.ara[j][i];
        }
    return temp;
}

int main()
{
    freopen("transform.in","r",stdin);
    freopen("transform.out","w",stdout);
    Matrix a,b,c;
    int ans=7;
    int x;
    cin>>x;
    a.set_n(x);
    b.set_n(x);
    cin>>a;
    cin>>b;
    if(b==Rotate_90(a))
        ans=min(ans,1);
    else if(b==Rotate_180(a))
        ans=min(ans,2);
    else if(b==Rotate_270(a))
        ans=min(ans,3);
    Matrix d;
    d.set_n(a.get_n());
    d=Reflex(a);
    if(b==d)
        ans=min(ans,4);
    for(int i=0; i<3; i++)
    {
        d=Rotate_90(d);
        if(b==d)
            ans=min(ans,5);
    }
    if(a==b)
        ans=min(ans,7);
    cout<<ans<<endl;
    return 0;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s