【USACO 1.2.2】方块转换

【问题描述】

一块N x N（1<=N<=10）正方形的黑白瓦片的图案要被转换成新的正方形图案。写一个程序来找出将原始图案按照以下列转换方法转换成新图案的最小方式：

1：转90度：图案按顺时针转90度。

2：转180度：图案按顺时针转180度。

3：转270度：图案按顺时针转270度。

4：反射：图案在水平方向翻转（以中央铅垂线为中心形成原图案的镜像）。

5：组合：图案在水平方向翻转，然后再按照1到3之间的一种再次转换。

6：不改变：原图案不改变。

7：无效转换：无法用以上方法得到新图案。

如果有多种可用的转换方法，请选择序号最小的那个。

一个步骤就要搞定

【格式】

INPUT FORMAT:

file (transformations.in)

第一行：单独的一个整数N。

第二行到第N+1行： N行每行N个字符（不是“@”就是“-”）；这是转换前的正方形。

第N+2行到第2*N+1行： N行每行N个字符（不是“@”就是“-”）；这是转换后的正方形。

OUTPUT FORMAT:

file (transformations.out)

单独的一行包括1到7之间的一个数字（在上文已描述）表明需要将转换前的正方形变为转换后的正方形的转换方法。

【分析】

模拟，压位。

只提醒一个地方：如果有多种可用的转换方法，请选择序号最小的那个。

  1 #include <cstdlib>
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <cstring>
  7 const int maxn=15;
  8 const int INF=0x7fffffff;
  9 using namespace std;
 10 int n;
 11 struct pic
 12 {
 13        int data[15];
 14        //比较运算符 
 15        bool operator ==(const pic &b)const
 16        {
 17             int i,flag=1;
 18             for (i=1;i<=n;i++)
 19             {
 20                 if (data[i]!=b.data[i])
 21                 {
 22                     flag=0;
 23                     break;
 24                 } 
 25             } 
 26             return flag;
 27        }
 28 }from,to;
 29 
 30 void init(pic &t);//输入 
 31 void solve();
 32 void turn(pic &t);//旋转90度 
 33 void fc(pic &t);//反射 
 34 
 35 int main()
 36 {
 37     //文件操作
 38     freopen("transformations.in","r",stdin);
 39     freopen("transformations.out","w",stdout); 
 40     
 41     scanf("%d",&n);
 42     init(from);
 43     init(to);
 44     solve();//解决 
 45     return 0;
 46 }
 47 void init(pic &t)
 48 {
 49      int i,j;
 50      memset(t.data,0,sizeof(t.data));
 51      for (i=1;i<=n;i++)
 52      {
 53          char str[maxn];
 54          scanf("%s",str);
 55          for (j=0;j<n;j++)
 56          t.data[i]=(t.data[i]<<1)+(str[j]=='-'?0:1);
 57      }
 58      return;
 59 }
 60 void solve()
 61 {
 62      pic temp=from;
 63      //旋转三次 
 64      turn(temp);if (temp==to) {printf("1");return;}
 65      turn(temp);if (temp==to) {printf("2");return;}
 66      turn(temp);if (temp==to) {printf("3");return;}
 67      
 68      temp=from;
 69      fc(temp);if (temp==to) {printf("4");return;}
 70      turn(temp);if (temp==to) {printf("5");return;}
 71      turn(temp);if (temp==to) {printf("5");return;}
 72      turn(temp);if (temp==to) {printf("5");return;}
 73      if (from==to) {printf("6
");return;}
 74      printf("7
");//无法获得 
 75      return;
 76 }
 77 void turn(pic &t)
 78 {
 79      int i,j;
 80      pic c;
 81      memset(c.data,0,sizeof(c.data));
 82      for (i=n;i>=1;i--)
 83      {
 84          for (j=1;j<=n;j++)
 85          {
 86              int temp;
 87              temp=(((1<<(j-1))&t.data[i])==(1<<(j-1)));
 88              c.data[n-j+1]=(c.data[n-j+1]<<1)+temp;
 89          }
 90      }
 91      t=c;
 92 }
 93 void fc(pic &t)
 94 {
 95      int i,j;
 96      pic c;
 97      memset(c.data,0,sizeof(c.data));
 98      for (i=1;i<=n;i++)
 99      {
100          //从左边一位一位取 
101          for (j=1;j<=n;j++)
102          {
103              int temp;
104              temp=(((1<<(j-1))&t.data[i])==(1<<(j-1)));
105              c.data[i]=(c.data[i]<<1)+temp;
106          }
107      }
108      t=c;
109 }