P1205 [USACO1.2] 方块转换 Transformations 题解

传送门

题意理解与强调

读入一个 $n \times n$ 的矩阵。注意字符串的读入方式！

转 $90\degree$：图案按顺时针转 $90\degree$。
转 $180\degree180°$：图案按顺时针转 $180\degree$。
转 $270\degree$：图案按顺时针转 $270\degree$。
反射：图案在水平方向翻转（以中央铅垂线为中心形成原图案的镜像）。
组合：图案在水平方向翻转，然后再按照 $1 \sim 3$ 之间的一种再次转换。
不改变：原图案不改变。
无效转换：无法用以上方法得到新图案。

如果有多种可用的转换方法，请选择序号最小的那个！ 所以需要注意判断的顺序。

只使用上述 $7$ 个中的一个步骤来完成这次转换。注意序号不要排错

题解

读入问题

如果一直过不了的话，可能是输入问题，注意行末回车。代码如下。

scanf("%d",&n);
for(int i=0;i<n;i++){
    scanf("%s",f[i]);
}
for(int i=0;i<n;i++){
    scanf("%s",t[i]);
}

解决不同角度的旋转问题

前三种操作我们可以看成是一种操作：第一个步骤是旋转 $90 \degree$ ，第二个步骤是在第一个步骤的基础上再旋转 $90 \degree$ ，第三步操作同理，那么我们可以每次旋转 $90 \degree$ 然后判断是否满足条件。最后再旋转 $90 \degree$ 即可恢复原状。

如何旋转

观察下面例子：

@-@   经过一次旋转   @-@
--@   ---------->   ---
@--                 -@@

设左上角的坐标为 $(0,0)$ 某一点的坐标为 $(i,j)$ （下同）,那么旋转 $90 \degree$ 的坐标是 $(j,n-i-1)$ ，于是得到代码如下。

void turn(){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            s[j][n-i-1]=f[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            f[i][j]=s[i][j];
        }
    }
    return;
}

如何翻转

这里的镜像是水平方向翻转，那么观察下面的例子：

@--   经过一次翻转   --@
--@   ---------->   @--
-@-                 -@-

水平方向翻转之后的坐标是 $(i,n-j-1)$ ，于是得到代码如下。

void flax(){
    for(int i=0;i<n;i++){
        for(int j=0;j<n/2;j++){
            char ch=f[i][j];
            f[i][j]=f[i][n-j-1];
            f[i][n-j-1]=ch;
        }
    }
    return;
}

如何判断答案是否满足条件

逐位判断即可。代码如下。

bool judge(){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            if(f[i][j]!=t[i][j])
                return false;
    }
    return true;
}

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[15][15],f[15][15],t[15][15];
int n;
void turn(){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            s[j][n-i-1]=f[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            f[i][j]=s[i][j];
        }
    }
    return;
}
void flax(){
    for(int i=0;i<n;i++){
        for(int j=0;j<n/2;j++){
            char ch=f[i][j];
            f[i][j]=f[i][n-j-1];
            f[i][n-j-1]=ch;
        }
    }
    return;
}
bool judge(){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            if(f[i][j]!=t[i][j])
                return false;
    }
    return true;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%s",f[i]);
    }
    for(int i=0;i<n;i++){
        scanf("%s",t[i]);
    }
    turn();
    if(judge()){
        printf("1");
        return 0;
    };
    turn();
    if(judge()){
        printf("2");
        return 0;
    }
    turn();
    if(judge()){
        printf("3");
        return 0;
    }
    turn();
    flax();
    if(judge()){
        printf("4");
        return 0;
    }
    for(int i=1;i<=3;i++){
        turn();
        if(judge()){
            printf("5");
            return 0;
        }
    }
    turn();
    flax();
    if(judge()){
        printf("6");
        return 0;
    }
    printf("7");
    return 0;
}