首页 > 代码库 > 【USACO】Transformations

【USACO】Transformations

2024-07-04 14:23:58   228人阅读

A square pattern of size N x N (1 <= N <= 10) black and white square tiles is transformed into another square pattern. Write a program that will recognize the minimum transformation that has been applied to the original pattern given the following list of possible transformations:

  • #1: 90 Degree Rotation: The pattern was rotated clockwise 90 degrees.
  • #2: 180 Degree Rotation: The pattern was rotated clockwise 180 degrees.
  • #3: 270 Degree Rotation: The pattern was rotated clockwise 270 degrees.
  • #4: Reflection: The pattern was reflected horizontally (turned into a mirror image of itself by reflecting around a vertical line in the middle of the image).
  • #5: Combination: The pattern was reflected horizontally and then subjected to one of the rotations (#1-#3).
  • #6: No Change: The original pattern was not changed.
  • #7: Invalid Transformation: The new pattern was not obtained by any of the above methods.

In the case that more than one transform could have been used, choose the one with the minimum number above.

PROGRAM NAME: transform

INPUT FORMAT

Line 1: A single integer, N
Line 2..N+1: N lines of N characters (each either `@‘ or `-‘); this is the square before transformation
Line N+2..2*N+1: N lines of N characters (each either `@‘ or `-‘); this is the square after transformation

SAMPLE INPUT (file transform.in)

3
@-@
---
@@-
@-@
@--
--@

OUTPUT FORMAT

A single line containing the the number from 1 through 7 (described above) that categorizes the transformation required to change from the `before‘ representation to the `after‘ representation.

SAMPLE OUTPUT (file transform.out)

1
一A的题，好happy。
不难，就是很麻烦。我是把前四个操作写成四个函数。其中旋转90度作为基本的函数，旋转180和旋转270都是由两次和三次旋转90度得到。
主要的问题就是int**和int a[][11]这两种传递参数时候遇到的麻烦，不知道怎么把两者统一起来，所以每次都要先把int**复制到一个数组里面，再作为参数传递给下一个函数，下午去找找资料吧。
  1 /*ID:Moment1991
  2   PROG:transform
  3   LANG:C++
  4   Compiling...
  5   Compile: OK
  6 
  7   Executing...
  8    Test 1: TEST OK [0.000 secs, 3496 KB]
  9    Test 2: TEST OK [0.003 secs, 3496 KB]
 10    Test 3: TEST OK [0.008 secs, 3496 KB]
 11    Test 4: TEST OK [0.008 secs, 3496 KB]
 12    Test 5: TEST OK [0.005 secs, 3496 KB]
 13    Test 6: TEST OK [0.003 secs, 3496 KB]
 14    Test 7: TEST OK [0.005 secs, 3496 KB]
 15    Test 8: TEST OK [0.005 secs, 3496 KB]
 16 
 17 All tests OK.
 18  */
 19 #include <iostream>
 20 #include <fstream>
 21 #include <stdlib.h>
 22 using namespace std;
 23 
 24 //旋转90度的操作
 25 int **transiformation_one(int before[][11],int n){
 26     int **tran = new int*[11];
 27     for(int i = 0;i < 11;i++){
 28         tran[i] = new int[11];
 29     }
 30     for(int i = 0;i < n;i++)
 31         for(int j = 0;j < n;j ++){
 32             tran[j][n-i-1] = before[i][j];
 33         }
 34     return tran;
 35 }
 36 
 37 //旋转180由两次旋转90度得到
 38 int **transiformation_two(int before[][11],int n){
 39     int **tran_1 = transiformation_one(before,n);
 40     int temp[11][11];
 41     for(int i = 0;i < n;i++)
 42         for(int j = 0;j < n;j ++)
 43             temp[i][j] = tran_1[i][j];
 44     int **tran_2 = transiformation_one(temp,n);
 45     return tran_2;
 46 }
 47 
 48 //旋转270由三次旋转90度得到
 49 int **transiformation_three(int before[][11],int n){
 50     int **tran_1 = transiformation_one(before,n);
 51     int temp[11][11];
 52     for(int i = 0;i < n;i++)
 53         for(int j = 0;j < n;j ++)
 54             temp[i][j] = tran_1[i][j];
 55 
 56     int **tran_2 = transiformation_one(temp,n);
 57     for(int i = 0;i < n;i++)
 58         for(int j = 0;j < n;j ++)
 59             temp[i][j] = tran_2[i][j];
 60 
 61     int **tran_3 = transiformation_one(temp,n);
 62     return tran_3;
 63 }
 64 
 65 //沿竖直方向翻转
 66 int **transiformation_four(int before[][11],int n){
 67     int **tran = new int*[11];
 68     for(int i = 0;i < 11;i++){
 69         tran[i] = new int[11];
 70     }
 71 
 72     for(int j = 0;j <= n/2;j++){
 73         for(int i = 0;i < n;i ++){
 74             tran[i][n-j-1] = before[i][j];
 75             tran[i][j] = before[i][n-j-1];
 76         }
 77     }
 78     return tran;
 79 }
 80 
 81 //判断两个矩阵是否相等
 82 bool is_equal(int **tran,int after[][11],int n){
 83     for(int i = 0;i < n;i ++)
 84         for(int j = 0;j < n;j ++)
 85             if(tran[i][j] != after[i][j]){
 86                 return false;
 87             }
 88     return true;
 89 }
 90 
 91 //没办法统一int**和inta[][11]，只好写两个判断相等函数
 92 bool another_equal(int tran[][11],int after[][11],int n){
 93     for(int i = 0;i < n;i ++)
 94         for(int j = 0;j < n;j ++)
 95             if(tran[i][j] != after[i][j])
 96                 return false;
 97     return true;
 98 }
 99 
100 int main(){
101     ifstream cin("transform.in");
102     ofstream cout("transform.out");
103 
104     int n;
105     char a;
106     int before[11][11];
107     int after[11][11];
108 
109     cin >> n;
110     for(int i = 0;i < n;i++)
111         for(int j = 0;j < n;j++){
112             cin >> a;
113             if(a == ‘@‘)
114                 before[i][j] = 0;
115             else
116                 before[i][j] = 1;
117         }
118 
119     for(int i = 0;i < n;i++)
120         for(int j = 0;j < n;j++)
121         {
122             cin >> a;
123             if(a == ‘@‘)
124                 after[i][j] = 0;
125             else
126                 after[i][j] = 1;
127         }
128 
129     int **tran = transiformation_one(before,n);
130     if(is_equal(tran,after,n))
131     {
132         cout <<1<<endl;
133         free(tran);
134         return 0;
135     }
136 
137     tran = transiformation_two(before,n);
138     if(is_equal(tran,after,n))
139     {
140         cout <<2<<endl;
141         free(tran);
142         return 0;
143     }
144 
145     tran = transiformation_three(before,n);
146     if(is_equal(tran,after,n))
147     {
148         cout <<3<<endl;
149         free(tran);
150         return 0;
151     }
152 
153     tran = transiformation_four(before,n);
154     if(is_equal(tran,after,n))
155     {
156         cout <<4<<endl;
157         free(tran);
158         return 0;
159     }
160 
161     //组合操作，调用多个函数实现
162     tran = transiformation_four(before,n);
163 
164     int temp[11][11];
165     for(int i = 0;i < n;i++)
166         for(int j = 0;j < n;j ++)
167             temp[i][j] = tran[i][j];
168     int **tran_2 = transiformation_one(temp,n);
169 
170     if(is_equal(tran_2,after,n))
171     {
172         cout <<5<<endl;
173         free(tran);
174         free(tran_2);
175         return 0;
176     }
177     else{
178         tran_2 = transiformation_two(temp,n);
179         if(is_equal(tran_2,after,n))
180         {
181             cout <<5<<endl;
182             free(tran);
183             free(tran_2);
184             return 0;
185         }
186     }
187     tran_2 = transiformation_three(temp,n);
188     if(is_equal(tran_2,after,n))
189     {
190         cout <<5<<endl;
191         free(tran);
192         free(tran_2);
193         return 0;
194     }
195 
196     if(another_equal(before,after,n))
197     {
198         cout << 6<<endl;
199         return 0;
200     }
201 
202     cout <<7<<endl;
203     return 0;
204 
205 }

 

 


联系
我们