P1205 [USACO1.2]方块转换 Transformations

题目链接：https://www.luogu.com.cn/problem/P1205

思路来源于本题题解第一位的CJXJR大佬。

隐藏在复杂外表下的大模拟，确实吓退了像我这样的小白。

将原题一点一点分解，其实本题考察的是矩阵的变化问题

但是我好像又做麻烦了，之后继续改进。主要是这个旋转，我开的数组太多了，之后考虑换一种旋转方法试试。

首先定义5个矩阵

1 char a[15][15]; //存储原矩阵
2 char b[15][15]; //存储要变换成的最终矩阵
3 char c[15][15]; //存储变换后的矩阵，也就是需要和最终矩阵对照的矩阵
4 char d[15][15]; //a矩阵的备份，防止a矩阵被改变
5 char e[15][15]; //用于work5的备份

定义比较函数，用于比较b矩阵和c矩阵是否相等

 1 bool check() {
 2     for (int i = 1; i <= n; i++) {
 3         for (int j = 1; j <= n; j++) {
 4             if (b[i][j] != c[i][j]) {
 5                 return false;
 6             }
 7         }
 8     }
 9     return true;
10 }

题目一共给了7个步骤，依次考虑每种情况

第一种情况，T = 1时，顺时针旋转90度

假设，n = 3时，原数组a[ ][ ]下标是

11　　12　　13

21　　22　　23

31　　32　　33

那么顺时针旋转90度后，就是c[ ][ ]为

31　　21　　11

32　　22　　12

33　　23　　13

把对应关系列成表，找规律

n　　ai　　aj　　ci　　cj

3　　1　　1　　 1　　 3　

3　　1　　2　　 2　　 3

3　　1　　3　　 3　　 3

3　　2　　1　　 1　　 2

3　　2　　2　　 2 　　2

3　　2　　3　　 3　　 2

3　　3　　1 　　1　　 1

3　　3　　2　　 2 　　1

3　　3　　3　　 3　　 1

找到对应关系c[j][n - i + 1] = a[i][j]

于是得出函数work1，用于判断原矩阵能否通过1操作变成最终矩阵

1 bool work1() {
2     for (int i = 1; i <= n; i++) {
3         for (int j = 1; j <= n; j++) {
4             c[j][n - i + 1] = d[i][j];
5         }
6     }
7     return check();
8 }

第二种情况，T = 2时，顺时针旋转180度，也可以像上面一样找规律，不过也可以看做是进行了两次T = 1顺时针旋转90度操作

于是得出函数work2，用于判断原矩阵能否通过2操作变成最终矩阵

 1 bool work2() {
 2     bool t = work1(); //第一次顺时针旋转90度，用变量t接受个返回值
 3     for (int i = 1; i <= n; i++) { //重置矩阵
 4         for (int j = 1; j <= n; j++) {
 5             d[i][j] = c[i][j];  
 6         }
 7     }
 8     t = work1();  //第二次顺时针旋转90度
 9     return t;
10 }

第三种情况，T = 3时，顺时针旋转270度，可以看做是进行了一次T = 1顺时针旋转90度操作，和一次T = 2顺时针旋转180度

于是得出函数work3，用于判断原矩阵能否通过3操作变成最终矩阵

 1 bool work3() {
 2     bool t = work1();  //第一次操作
 3     for (int i = 1; i <= n; i++) { //重置矩阵
 4         for (int j = 1; j <= n; j++) {
 5             d[i][j] = c[i][j];   
 6         }
 7     }
 8     t = work2();   //第二次操作
 9     return t;
10 }

第四种情况，T = 4时，水平方向左右反转

假设，n = 3时，原数组a[ ][ ]下标是

11　　12　　13

21　　22　　23

31　　32　　33

那么水平翻转后，就是c[ ][ ]为

13　　12　　11

23　　22　　21

33　　32　　31

把对应关系列成表，找规律

n　　ai　　aj　　ci　　cj

3　　1　　1　　 1　　 3　

3　　1　　2　　 1　　 2

3　　1　　3　　 1　　 1

3　　2　　1　　 2　　 3

3　　2　　2　　 2 　　2

3　　2　　3　　 2　　 1

3　　3　　1 　　3　　 3

3　　3　　2　　 3 　　 2

3　　3　　3　　 3　　 1

找到对应关系c[i][n - j + 1] = a[i][j]

于是得出函数work4，用于判断原矩阵能否通过4操作变成最终矩阵

1 bool work4() {
2     for (int i = 1; i <= n; i++) {
3         for (int j = 1; j <= n; j++) {
4             c[i][n - j + 1] = a[i][j];
5         }
6     }
7     return check();
8 }

第五种情况，T = 5时，这个是多种情况的组合，4和1，或4和2，或4和3，

有一个能行就行。明白了上面的，就容易得出work5，用于判断原矩阵能否通过5操作变成最终矩阵

 1 bool work5() {
 2     bool t = work4(); //先水平翻转,现在c里存的是水平翻转后的a
 3     for (int i = 1; i <= n; i++) {
 4         for (int j = 1; j <= n; j++) {
 5             e[i][j] = c[i][j];
 6         }
 7     }
 8     for (int i = 1; i <= n; i++) {
 9         for (int j = 1; j <= n; j++) {
10             d[i][j] = c[i][j];
11         }
12     }
13     if (work1()) {
14         return true;
15     }
16     for (int i = 1; i <= n; i++) {
17         for (int j = 1; j <= n; j++) {
18             c[i][j] = e[i][j];
19         }
20     }
21     for (int i = 1; i <= n; i++) {
22         for (int j = 1; j <= n; j++) {
23             d[i][j] = e[i][j];
24         }
25     }
26     if (work2()) {
27         return true;
28     }
29     for (int i = 1; i <= n; i++) {
30         for (int j = 1; j <= n; j++) {
31             c[i][j] = e[i][j];
32         }
33     } 
34     for (int i = 1; i <= n; i++) {
35         for (int j = 1; j <= n; j++) {
36             d[i][j] = e[i][j];
37         }
38     }
39     if (work3()) {
40         return true;
41     }
42     return false;
43 }

第六种情况，T = 6时，直接比较

 1 bool work6() {
 2     for (int i = 1; i <= n; i++) {
 3         for (int j = 1; j<= n; j++) {
 4             if (a[i][j] != b[i][j]) {
 5                 return false;
 6             }
 7         }
 8     }
 9     return true;
10 }

注意题目中的：如果有多种可用的转换方法，请选择序号最小的那个。

就是说从1~7一个一个看，check成功就直接输出对应的编号

AC代码

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 int n;
  4 char a[15][15]; //存储原矩阵
  5 char b[15][15]; //存储要变换成的最终矩阵
  6 char c[15][15]; //存储变换后的矩阵，也就是需要和最终矩阵对照的矩阵
  7 char d[15][15]; //a矩阵的备份，防止a矩阵被改变
  8 char e[15][15]; //用于work5的备份
  9 bool check() { //判断b矩阵和c矩阵是否相同
 10     for (int i = 1; i <= n; i++) {
 11          for (int j = 1; j <= n; j++) {
 12              if (b[i][j] != c[i][j]) {
 13                 return false;
 14             }
 15         }
 16     }
 17     return true;
 18 }
 19 bool work1() {
 20     for (int i = 1; i <= n; i++) {
 21         for (int j = 1; j <= n; j++) {
 22             c[j][n - i + 1] = d[i][j];
 23         }
 24     }
 25     return check();
 26 }
 27 bool work2() {
 28     bool t = work1(); //第一次顺时针旋转90度，用变量t接受个返回值
 29     for (int i = 1; i <= n; i++) { //重置矩阵
 30         for (int j = 1; j <= n; j++) {
 31             d[i][j] = c[i][j];  
 32         }
 33     }
 34     t = work1();  //第二次顺时针旋转90度
 35     return t;
 36 }
 37 bool work3() {
 38     bool t = work1();  //第一次操作
 39     for (int i = 1; i <= n; i++) { //重置矩阵
 40         for (int j = 1; j <= n; j++) {
 41             d[i][j] = c[i][j];   
 42         }
 43     }
 44     t = work2();   //第二次操作
 45     return t;
 46 }
 47 bool work4() {
 48     for (int i = 1; i <= n; i++) {
 49         for (int j = 1; j <= n; j++) {
 50             c[i][n - j + 1] = a[i][j];
 51         }
 52     }
 53     return check();
 54 }
 55 bool work5() {
 56     bool t = work4(); //先水平翻转,现在c里存的是水平翻转后的a
 57     for (int i = 1; i <= n; i++) {
 58         for (int j = 1; j <= n; j++) {
 59             e[i][j] = c[i][j];
 60         }
 61     }
 62     for (int i = 1; i <= n; i++) {
 63         for (int j = 1; j <= n; j++) {
 64             d[i][j] = c[i][j];
 65         }
 66     }
 67     if (work1()) {
 68         return true;
 69     }
 70     for (int i = 1; i <= n; i++) {
 71         for (int j = 1; j <= n; j++) {
 72             c[i][j] = e[i][j];
 73         }
 74     }
 75     for (int i = 1; i <= n; i++) {
 76         for (int j = 1; j <= n; j++) {
 77             d[i][j] = e[i][j];
 78         }
 79     }
 80     if (work2()) {
 81         return true;
 82     }
 83     for (int i = 1; i <= n; i++) {
 84         for (int j = 1; j <= n; j++) {
 85             c[i][j] = e[i][j];
 86         }
 87     } 
 88     for (int i = 1; i <= n; i++) {
 89         for (int j = 1; j <= n; j++) {
 90             d[i][j] = e[i][j];
 91         }
 92     }
 93     if (work3()) {
 94         return true;
 95     }
 96     return false;
 97 }
 98 bool work6() {
 99     for (int i = 1; i <= n; i++) {
100         for (int j = 1; j<= n; j++) {
101             if (a[i][j] != b[i][j]) {
102                 return false;
103             }
104         }
105     }
106     return true;
107 }
108 void work() {
109     if (work1()) {
110         cout << 1 << endl;
111         return;
112     }
113     if (work2()) {
114         cout << 2 << endl;
115         return;
116     }
117     if (work3()) {
118         cout << 3 << endl;
119         return;
120     }
121     if (work4()) {
122         cout << 4 << endl;
123         return;
124     }
125     if (work5()) {
126         cout << 5 << endl;
127         return;
128     }
129     if (work6()) {
130         cout << 6 << endl;
131         return;
132     }
133     cout << 7 << endl;
134 }
135 int main() {
136     cin >> n;
137     for (int i = 1; i <= n; i++) {
138         for (int j = 1; j <= n; j++) {
139              cin >> a[i][j];
140              d[i][j] = a[i][j];
141              e[i][j] = a[i][j];
142         }
143     }
144     for (int i = 1; i <= n; i++) {
145         for (int j = 1; j <= n; j++) {
146             cin >> b[i][j];
147         }
148     }
149     work();
150     return 0; 
151 }