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

CJXJR · 2019-06-02 14:38:47 · 题解

大模拟！！！

说实话，我认为本题的算法并不是搜索，而是模拟，题目已经很明确的说了，n一共有7种情况，我们把这七种情况一个一个分情况讨论，答案就出来了。

由于题目要求将每一次所变换的图形与原图形进行比较，所以定义数组a[15][15],b[15][15],c[15][15],d[15][15](\text{题目申明}1 \leq n\leq10),a数组表示第一个输入的矩阵，b数组表示变换后的矩阵，c数组表示要对照的矩阵，d数组为将要存放的矩阵，所以可以写出以下判断b矩阵与c矩阵相同的代码
↓↓↓

for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
     if(b[i][j]!=c[i][j])
     return 0;
     return 1;

简单明了，蒟蒻都能懂！

设原矩阵为↓↓↓

11 12 13
21 22 23
31 32 33

那么，经过顺时针转90度的矩阵为

31 21 11
32 22 12
33 23 13

列出i(行)与j(列)的关系，如下：

再进行找规律，经推敲可得

再与前面所说的判断合在一起，可得：

bool work1()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        b[j][n-i+1]=a[i][j];
    }
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
     if(b[i][j]!=c[i][j])
     return 0;
     return 1;
}

#include<bits/stdc++.h>
using namespace std;
int n;
char a[15][15],b[15][15],c[15][15],d[15][15];
bool work1()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        b[j][n-i+1]=a[i][j];
    }
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
     if(b[i][j]!=c[i][j])
     return 0;
     return 1;
}
bool work2()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        b[n-i+1][n-j+1]=a[i][j];
    }
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
     if(b[i][j]!=c[i][j])
     return 0;
     return 1;
}
bool work3()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        b[n-j+1][i]=a[i][j];
    }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
     if(b[i][j]!=c[i][j])
     return 0;
     return 1;
}
bool work4()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        b[i][n-j+1]=a[i][j];
    }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
     if(b[i][j]!=c[i][j])
     return 0;
     return 1;
}
bool work5()
{
    work4();
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      a[i][j]=b[i][j];  
      if(work1())
      return 1;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      a[i][j]=b[i][j]; 
      if(work2())
      return 1;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      a[i][j]=b[i][j]; 
      if(work3())
      return 1;
      return 0;
}
bool work6()
{
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
     if(b[i][j]!=c[i][j])
     return 0;
     return 1;
}
void work()
{
    if(work1())
    {
        cout<<1;
        return ;
    }
    if(work2())
    {
        cout<<2;
        return ;
    }
    if(work3())
    {
        cout<<3;
        return ;
    }
    if(work4())
    {
        cout<<4;
        return ;
    }
    if(work5())
    {
        cout<<5;
        return ;
    }
    if(work6())
    {
        cout<<6;
        return ;
    }
    cout<<7;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
     {
        cin>>a[i][j];
        d[i][j]=a[i][j];
     }

    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      cin>>c[i][j];
    work();
    return 0; //完美的结束QAQ
}