P1205 [USACO1.2] 方块转换 Transformations

洛谷做题日志

P1205 [USACO1.2] 方块转换 Transformations

题目描述

一块 $n \times n$ 正方形的黑白瓦片的图案要被转换成新的正方形图案。写一个程序来找出将原始图案按照以下列转换方法转换成新图案的最小方式:

  • 转 $90\degree$:图案按顺时针转 $90\degree$。

  • 转 $180\degree$:图案按顺时针转 $180\degree$。

  • 转 $270\degree$:图案按顺时针转 $270\degree$。

  • 反射:图案在水平方向翻转(以中央铅垂线为中心形成原图案的镜像)。

  • 组合:图案在水平方向翻转,然后再按照 $1 \sim 3$ 之间的一种再次转换。

  • 不改变:原图案不改变。

  • 无效转换:无法用以上方法得到新图案。

如果有多种可用的转换方法,请选择序号最小的那个。

只使用上述 $7$ 个中的一个步骤来完成这次转换。

输入格式

第一行一个正整数 $n$。

然后 $n$ 行,每行 $n$ 个字符,全部为 @-,表示初始的正方形。

接下来 $n$ 行,每行 $n$ 个字符,全部为 @-,表示最终的正方形。

输出格式

单独的一行包括 $1 \sim 7$ 之间的一个数字(在上文已描述)表明需要将转换前的正方形变为转换后的正方形的转换方法。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
3
@-@
---
@@-
@-@
@--
--@

样例输出 #1

1
1

提示

【数据范围】
对于 $100%$ 的数据,$1\le n \le 10$。

题目翻译来自 NOCOW。

USACO Training Section 1.2

解答

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
using namespace std; 
struct matrix
{
    char a[12][12];
    int dim;
}A,B;
matrix Real_Reflex(matrix x)
{
    int n = x.dim;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n/2;j++)
        {
            int temp = x.a[i][j];
            x.a[i][j] = x.a[i][n-j-1];
            x.a[i][n-j-1] = temp;
        }
    }
    return x;
}
matrix Real_Rorate(matrix x)
{
    int n = x.dim;
    for(int i=0;i<n/2;i++)
    {
        for(int j=i;j<n-i-1;j++)
        {
            int temp = x.a[i][j];
            x.a[i][j] = x.a[n-j-1][i];
            x.a[n-j-1][i] = x.a[n-i-1][n-j-1];
            x.a[n-i-1][n-j-1] = x.a[j][n-i-1];
            x.a[j][n-i-1] = temp;
        }
    }
    return x;

}
int Are_they_the_same(matrix X)
{
    int n = X.dim;
    int flag = 0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(X.a[i][j]!=B.a[i][j])
            {
                flag = 1;
                break;
            }
        }
    }
    if(flag==0)
    {
        return 1;
    }
    return 0;
}
int main()
{
    int n;
    cin>>n;
    A.dim = n;
    B.dim = n;
    for(int i=0;i<n;i++)//cin the matrixA
    {
        for(int j=0;j<n;j++)
        {
            cin>>A.a[i][j];
        }
    }
    for(int i=0;i<n;i++)//cin the matrixB
    {
        for(int j=0;j<n;j++)
        {
            cin>>B.a[i][j];
        }
    }

    if(Are_they_the_same(Real_Rorate(A))==1)//rorate 90 degrees
    {
        cout<<"1";
        return 0;
    }
    else if(Are_they_the_same(Real_Rorate(Real_Rorate(A))))//rorate 180 degrees
    {
        cout<<"2";
        return 0;
    }
    else if(Are_they_the_same(Real_Rorate(Real_Rorate(Real_Rorate(A)))))//rorate 270 degrees
    {
        cout<<"3";
        return 0;
    }
    else if(Are_they_the_same(Real_Reflex(A))==1)//reflex
    {
        cout<<"4";
        return 0;
    }
    else if(Are_they_the_same(Real_Rorate(Real_Reflex(A)))==1)//rorate 90 degrees and reflex
    {
        cout<<"5";
        return 0;
    }
    else if(Are_they_the_same(Real_Rorate(Real_Rorate(Real_Reflex(A))))==1)//rorate 180 degrees and reflex
    {
        cout<<"5";
        return 0;
    }
    else if(Are_they_the_same(Real_Rorate(Real_Rorate(Real_Rorate(Real_Reflex(A))))))//rorate 270 degrees and reflex
    {
        cout<<"5";
        return 0;
    }
    else if(Are_they_the_same(A))//no rorate
    {
        cout<<"6";
        return 0;
    }
    else
    {
        cout<<"7";
        return 0;
    }
    return 0;
}
Licensed under CC BY-NC-SA 4.0
Progress Infinite!
使用 Hugo 构建
主题 StackJimmy 设计