洛谷笔记 - 洛谷 P1205 [USACO1.2] 方块转换 Transformations

发表于 更新于 本文字数： 751 阅读时长 ≈ 3 分钟

超长超啰嗦代码警告！

题目描述

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

  • 转 90°90\degree：图案按顺时针转 90°90\degree。

  • 转 180°180\degree：图案按顺时针转 180°180\degree。

  • 转 270°270\degree：图案按顺时针转 270°270\degree。

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

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

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

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

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

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

输入格式

第一行一个正整数 nn。

然后 nn 行，每行 nn 个字符，全部为 @ 或 -，表示初始的正方形。

接下来 nn 行，每行 nn 个字符，全部为 @ 或 -，表示最终的正方形。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

1
1

提示

【数据范围】
对于 100%100\% 的数据，1≤n≤101\le n \le 10。

题目翻译来自 NOCOW。

USACO Training Section 1.2

代码部分

哆哆嗦嗦写了 90 多行，条理性…… 还可以？

本来打算使用 std:copy 函数弄函数备份及恢复来着，后来发现下不了手。

用的不熟的东西请谨慎使用！

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
//P1205 [USACO1.2] 方块转换 Transformations
//https://www.luogu.com.cn/problem/P1205

//https://www.luogu.com.cn/record/87542216
//https://www.luogu.com.cn/record/87542740

#include<iostream>
using namespace std;
int n;
char a[11][11],b[11][11],c[11][11];
bool check(int stage,bool check_not_in_stage_5th){
    for(int i=1;i<=n;i++){
        for(int o=1;o<=n;o++){
            if(b[i][o]!=c[i][o]){
                return 0;
            }
        }
    }
    if(check_not_in_stage_5th){
        cout<<stage<<endl;
    }else cout<<5<<endl;
    return 1;
}
void acr(){
    for(int i=1;i<=n;i++){
        for(int o=1;o<=n;o++){
            c[i][o]=a[i][o];
        }
    }
    return;
}
bool check_1to3(bool stage_in_5th){
    for(int i=1;i<=3;i++){
        char tmp[11][11];
        for(int y=1;y<=n;y++){
            for(int x=1;x<=n;x++){
                tmp[x][n-y+1]=c[y][x];
            }
        }
        for(int o=1;o<=n;o++){
            for(int p=1;p<=n;p++){
                c[o][p]=tmp[o][p];
            }
        }
        if(stage_in_5th){
            if(check(i,0)){
                return 1;
            }
        }else if(check(i,1)){
            return 1;
        }
    }
    return 0;
}
bool check_4to5(){
    char tmp[11][11];
    for(int y=1;y<=n;y++){
        for(int x=1;x<=n;x++){
            tmp[y][x]=c[y][n-x+1];
        }
    }
    for(int o=1;o<=n;o++){
        for(int p=1;p<=n;p++){
            c[o][p]=tmp[o][p];
        }
    }
    if(check(4,1)){
        return 1;
    }else{
        if(check_1to3(1)){
            return 1;
        }
    }
    return 0;
}
/// @brief 
/// @return 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int o=1;o<=n;o++){
            cin>>a[i][o];
            c[i][o]=a[i][o];
        }
    }
    for(int i=1;i<=n;i++){
        for(int o=1;o<=n;o++){
            cin>>b[i][o];
        }
    }
    if(check_1to3(0)==0){
        acr();
        if(check_4to5()==0){
            acr();
            if(check(6,1)==0){
                cout<<7<<endl;
            }
        }
    }
    return 0;
}