USACO Section 1.2.3 Transformations
题目
| <center style="font-size:14px;"> Transformations </center> 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:
In the case that more than one transform could have been used, choose the one with the minimum number above. PROGRAM NAME: transformINPUT FORMAT
SAMPLE INPUT (file transform.in)3 @-@ --- @@- @-@ @-- --@ OUTPUT FORMATA 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 |
思路
思路很简单，就是枚举各种转换方法，然后与莫状态进行比较。
繁琐即需要注意的是，对于每种转换方式 i和j的关系，稍有疏忽就会全军覆没
另外注意的就是：如果初末状态相同，不能直接输出6，要先看看之前的5种方法能不能得到。因为题目要求从小号优先。我就被坑了一次。
代码
/*
ID:zhrln1
PROG:transform
LANG:C++
*/
#include <cstdio>
int n;
typedef struct board{
char v[11][11];
} Board;
Board a,b;
Board rdboard(int n){
Board c;
for (int i(1);i<=n;i++){
for (int j(1);j<=n;j++){
scanf("%c",&c.v[i][j]);
}
scanf("\n");
}
return c;
}
Board change(Board a,int k,int n){
Board c;
for (int i(1);i<=n;i++){
for (int j(1);j<=n;j++){
switch(k){
case 1: c.v[i][j]=a.v[n-j+1][i];break;
case 2: c.v[i][j]=a.v[n+1-i][n+1-j];break;
case 3: c.v[i][j]=a.v[j][n+1-i];break;
case 4: c.v[i][j]=a.v[i][n+1-j];break;
}
}
}
return c;
}
int isequel(Board a,Board b,int n){
for (int i(1);i<=n;i++){
for (int j(1);j<=n;j++){
if (a.v[i][j]!=b.v[i][j]) return 0;
}
}
return 1;
}
int main(){
freopen("transform.in","r",stdin);
freopen("transform.out","w",stdout);
scanf("%d\n",&n);
a=rdboard(n);
b=rdboard(n);
for (int i(1);i<=4;i++){
Board t=change(a,i,n);
if (isequel(t,b,n)){
printf("%d\n",i);
return 0;
}
if (i==4){
for (int j(1);j<=3;j++){
if (isequel(change(t,j,n),b,n)){
printf("5\n");
return 0;
}
}
}
}
if (isequel(a,b,n)){
printf("6\n");
return 0;
}
printf("7\n");
return 0;
}
