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

· · 题解

这种题就是纯模拟，但是模拟最好是用模块化（函数）来写，否则很容易出错

我们每次操作大概的模型为:

for(int i=1,u=1;i<=n;++i,++u)
        for(int j=1,v=1;j<=n;++j,++v)
            out[u][v]=in[i][j];
目标是把$out$的$[u][v]$赋成$in$的$[i][j]

先来分析一下每种情况：

第一种
1 2 3
4 5 6
7 8 9

变为
7 4 1
8 5 2
9 6 3

发现123的坐标是行增加的(++u),147的坐标是列减少的(--v),那么就可以推出for循环：

for(int i=1,v=n;i<=n;++i,--v)
        for(int j=1,u=1;j<=n;++j,++u)
            out[u][v]=in[i][j];

第二种要变为：
9 8 7
6 5 4
3 2 1

发现123的坐标是列减少的(--v),147的坐标是行减少的(--u),那么就可以推出for循环：

for(int i=1,u=n;i<=n;++i,--u)
        for(int j=1,v=n;j<=n;++j,--v)
            out[u][v]=in[i][j];

第三种：
3 6 9
2 5 8
1 4 7

发现123的坐标是行减少的(--u),147的坐标是列增加的(++v),那么就可以推出for循环：

for(int i=1,v=1;i<=n;++i,++v)
        for(int j=1,u=n;j<=n;++j,--u)
            out[u][v]=in[i][j];

第四种：
3 2 1
6 5 4
9 8 7

发现123的坐标是列减少的(--v),147的坐标是行增加的(++u),那么就可以推出for循环：

for(int i=1,u=1;i<=n;++i,++u)
        for(int j=1,v=n;j<=n;++j,--v)
            out[i][j]=in[u][v];

到此为止，四种基本操作都写完了

第五种其实就是叫你先做一遍第四种操作，然后再做第一或第二或第三种操作，然后判断

第六种直接判断

判断的话就是里两个for，把out与给的转换后的正方形进行比较就好了

模块化见我代码：

#include <cstdio>
using namespace std;
const int MaxN=11;
char fin[MaxN][MaxN]; //给的转换后的正方形
int n;
void print(char a[][MaxN]) //传入二维数组
{                           //调试用的，输出这个二维数组
    for(int i=1;i<=n;++i)
        puts(a[i]+1);
    return;
}
bool pd(char a[][MaxN],char b[][MaxN]) //判断是否相同
{
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            if(a[i][j]^b[i][j]) // ^为异或，在这里可以理解为!=
                return false;
    return true;
}
bool _1(char mp[][MaxN])    //第一种操作
{
    char a[MaxN][MaxN];
    for(int i=1,v=n;i<=n;++i,--v)
        for(int j=1,u=1;j<=n;++j,++u)
            a[u][v]=mp[i][j];
    return pd(a,fin);
}
bool _2(char mp[][MaxN])    //第二种操作
{
    char a[MaxN][MaxN];
    for(int i=1,u=n;i<=n;++i,--u)
        for(int j=1,v=n;j<=n;++j,--v)
            a[u][v]=mp[i][j];
    return pd(a,fin);
}
bool _3(char mp[][MaxN])    //第三种操作
{
    char a[MaxN][MaxN];
    for(int i=1,v=1;i<=n;++i,++v)
        for(int j=1,u=n;j<=n;++j,--u)
            a[u][v]=mp[i][j];
    return pd(a,fin);
}
bool _4(char mp[][MaxN])    //第四种操作
{
    char a[MaxN][MaxN];
    for(int i=1,u=1;i<=n;++i,++u)
        for(int j=1,v=n;j<=n;++j,--v)
            a[i][j]=mp[u][v];
    return pd(a,fin);
}
bool _5(char mp[][MaxN])    //第五种操作
{
    char a[MaxN][MaxN];
    for(int i=1,u=1;i<=n;++i,++u)
        for(int j=1,v=n;j<=n;++j,--v)
            a[i][j]=mp[u][v];   //先做一边第四种操作
    if(_1(a))       //试一试第一种操作能不能是变换后的正方形相同
        return true;
    else if(_2(a))  //尝试第二种
        return true;
    else if(_3(a))  //尝试第三种
        return true;
    return false;
}
bool _6(char mp[][MaxN])    //第六种操作
{
    return pd(mp,fin);      //直接返回判断
}
int main(void)
{
    char mp[MaxN][MaxN];
    scanf("%d",&n);
    for(int i=1;i<=n;++i)   //读入原始正方形
        scanf("%s",mp[i]+1);    //+1是为了从下标1开始存储
    for(int i=1;i<=n;++i)
        scanf("%s",fin[i]+1);   //读入变换后正方形
    if(_1(mp))      //尝试每一种情况
        return puts("1"),0;
    else if(_2(mp))
        return puts("2"),0;
    else if(_3(mp))
        return puts("3"),0;
    else if(_4(mp))
        return puts("4"),0;
    else if(_5(mp))
        return puts("5"),0;
    else if(_6(mp))
        return puts("6"),0;
    return puts("7"),0;
}