Home > Old Blog Posts > USACO 1.2.2 Transformations

USACO 1.2.2 Transformations


旋转如何实现?

“把行存到列上”,具体的公式:

右转90度:b[j,n-i+1]:=a[i,j]

180,270可通过反复调用90度实现

水平翻转:b[i,n-j+1]:=a[i,j]

对初学者来说,可以用这道题练习结构化编程。

代码(这个代码大家当反面教材就好了,当时头脑发热想到用复数法来实现旋转,代码编了180行)

/*
ID: dementr1
PROG: transform
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<stdio.h>
using namespace std;
ifstream fin(“transform.in”);
ofstream fout(“transform.out”);
int n;
struct ord
{
int x,y;
};
void turn90(int from[][20],int to[][20])
{
int i,j,tmpx,tmpy,xx,yy,tmpfrom[20][20],tmpto[20][20];
ord dis[20][20];
int N=n;
if(n%2==0)N++;
for(i=0;i<n;i++)
for(j=0;j<n;j++) tmpfrom[i][j]=from[i][j];
if(n%2==0)
{
for(i=n/2+1;i<=n;i++)
for(j=0;j<n;j++)
tmpfrom[i][j]=from[i-1][j];
for(i=0;i<n/2;i++)
for(j=n/2+1;j<=n;j++)
tmpfrom[i][j]=from[i][j-1];
for(i=n/2+1;i<=n;i++)
for(j=n/2+1;j<=n;j++)
tmpfrom[i][j]=from[i-1][j-1];
for(i=0;i<=n;i++) tmpfrom[i][n/2]=0;
for(j=0;j<=n;j++) tmpfrom[n/2][j]=0;
}

for(i=0;i<N;i++)
for(j=0;j<N;j++)
{
dis[i][j].x=i-(N+1)/2+1;
dis[i][j].y=j-(N+1)/2+1;
}
for(i=0;i<N;i++)
for(j=0;j<N;j++)
{
dis[i][j].x*=(-1);
dis[i][j].y*=(-1);
tmpx=dis[i][j].x;
tmpy=dis[i][j].y;
dis[i][j].x=tmpy*(-1);
dis[i][j].y=tmpx;
}
for(i=0;i<N;i++)
for(j=0;j<N;j++)
{
xx=dis[i][j].x+(N+1)/2-1;
yy=dis[i][j].y+(N+1)/2-1;
tmpto[xx][yy]=tmpfrom[i][j];
}

for(i=0;i<N;i++)
for(j=0;j<N;j++) to[i][j]=tmpto[i][j];
if(n%2==0)
{
for(i=n/2;i<n;i++)
for(j=0;j<=N;j++)
to[i][j]=tmpto[i+1][j];
for(i=0;i<n/2;i++)
for(j=n/2;j<n;j++)
to[i][j]=tmpto[i][j+1];
for(i=n/2;i<n;i++)
for(j=n/2;j<n;j++)
to[i][j]=tmpto[i+1][j+1];
}
}
void turn180(int from[][20],int to[][20])
{
int to1[20][20];
turn90(from,to1);
turn90(to1,to);
}
void turn270(int from[][20],int to[][20])
{
int to1[20][20];
turn180(from,to1);
turn90(to1,to);
}
void reflect(int from[][20],int to[][20])
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
to[i][j]=from[i][n-j-1];
}
bool equal(int a[][20],int b[][20])
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(a[i][j]!=b[i][j]) return false;
return true;
}
int main()
{
string s;
int tmp[20][20],tmp1[20][20],tmp2[20][20],tmp3[20][20],i,j;
int from[20][20],to[20][20];
fin>>n;
for(i=0;i<n;i++)
{
fin>>s;
for(j=0;j<n;j++)
{
if(s[j]==’@’) from[i][j]=0;
if(s[j]==’-‘) from[i][j]=1;
}
}
for(i=0;i<n;i++)
{
fin>>s;
for(j=0;j<n;j++)
{
if(s[j]==’@’) to[i][j]=0;
if(s[j]==’-‘) to[i][j]=1;
}
}
memset(tmp,0,sizeof(tmp));
turn90(from,tmp);
if(equal(tmp,to))
{
fout<<1<<endl;
return 0;
}
memset(tmp,0,sizeof(tmp));
turn180(from,tmp);
if(equal(tmp,to))
{
fout<<2<<endl;
return 0;
}
memset(tmp,0,sizeof(tmp));
turn270(from,tmp);
if(equal(tmp,to))
{
fout<<3<<endl;
return 0;
}

memset(tmp,0,sizeof(tmp));
reflect(from,tmp);
if(equal(tmp,to))
{
fout<<4<<endl;
return 0;
}

memset(tmp,0,sizeof(tmp));
reflect(from,tmp);
turn90(tmp,tmp1);
turn180(tmp,tmp2);
turn270(tmp,tmp3);
if(equal(tmp1,to)||equal(tmp2,to)||equal(tmp3,to))
{
fout<<5<<endl;
return 0;
}

if(equal(from,to))
{
fout<<6<<endl;
return 0;
}
fout<<7<<endl;
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

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

%d bloggers like this: