题目描述
题目要求识别给定正方形图案经过的变换。可能的变换有：
- 90 Degree Rotation\texttt{90 Degree Rotation}90 Degree Rotation：顺时针旋转909090度
- 180 Degree Rotation\texttt{180 Degree Rotation}180 Degree Rotation：顺时针旋转180180180度
- 270 Degree Rotation\texttt{270 Degree Rotation}270 Degree Rotation：顺时针旋转270270270度
- Vertical Reflection\texttt{Vertical Reflection}Vertical Reflection：垂直反射（上下翻转）
- Combination\texttt{Combination}Combination：先垂直反射，再执行上述三种旋转之一
- Preservation\texttt{Preservation}Preservation：图案不变
- Improper\texttt{Improper}Improper：不能由以上任何变换得到
变换的优先级（工作量由小到大）为：Preservation < 90度旋转 < 180度旋转 < 270度旋转 < 垂直反射 < 垂直反射+90度 < 垂直反射+180度 < 垂直反射+270度。若图案可通过多种变换得到，输出工作量最小的那个。
输入格式
输入包含多个图案数据集。每个数据集第一行为整数nnn（1≤n≤101 \le n \le 101≤n≤10），表示图案的边长。接下来nnn行，每行包含两个字符串，各由nnn个字符组成（.表示亮，X表示暗），分别表示原始图案和变换后图案，中间用空格分隔。输入以文件结束符（EOF\texttt{EOF}EOF）终止。
输出格式
对于每个数据集，输出一行，格式为：
Pattern X was 变换描述.其中X为数据集编号（从111开始），变换描述为上述列表中的短语。
样例
输入
5 X...X ....X .X... ...X. ...X. .X... ..X.X ..X.. ....X XX..X 6 ....XX X....X ...X.. X.X... XX..X. .X..X. ..X... ...X.X ...X.. ..X... ..X..X ..X.. 2 X. X. .X .X 4 ..X. ...X XX.. .... .... XX.. ...X ..X. 5 X.... .X... .X... ..X.. .X... ..X.. ...X. ....X ....X X.... 4 .X.. ..X. .X.X X... .... ..XX ..X. .... 2 .. XX XX ..输出
Pattern 1 was rotated 90 degrees. Pattern 2 was rotated 270 degrees. Pattern 3 was preserved. Pattern 4 was reflected vertically. Pattern 5 was improperly transformed. Pattern 6 was reflected vertically and rotated 270 degrees. Pattern 7 was rotated 180 degrees.题目分析
本题的核心是实现图案的旋转变换和垂直反射，并按优先级顺序检查变换结果。
图案表示
将n×nn \times nn×n的图案存储为长度为n2n^2n2的字符串，按行主序排列（第111行从左到右，然后是第222行，依此类推）。
变换实现
- 顺时针旋转909090度：原位置(r,c)(r, c)(r,c)（000索引）映射到新位置(c,n−1−r)(c, n-1-r)(c,n−1−r)。在字符串中，原索引为r×n+cr \times n + cr×n+c，新索引为c×n+(n−1−r)c \times n + (n-1-r)c×n+(n−1−r)。
- 顺时针旋转180180180度：可将字符串整体反转。
- 顺时针旋转270270270度（即逆时针909090度）：原位置(r,c)(r, c)(r,c)映射到(n−1−c,r)(n-1-c, r)(n−1−c,r)。
- 垂直反射（上下翻转）：原位置(r,c)(r, c)(r,c)映射到(n−1−r,c)(n-1-r, c)(n−1−r,c)。
检查顺序
按工作量递增的顺序检查：
- 原始图案是否等于变换后图案（Preservation）
- 旋转909090度
- 旋转180180180度
- 旋转270270270度
- 垂直反射
- 垂直反射后再旋转909090度
- 垂直反射后再旋转180180180度
- 垂直反射后再旋转270270270度
- 若均不匹配，则为 Improper
复杂度分析
每种变换操作O(n2)O(n^2)O(n2)，n≤10n \le 10n≤10，完全可接受。
代码实现
// Mirror, Mirror// UVa ID: 466// Verdict: Accepted// Submission Date: 2016-07-21// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;stringrotateCW90(string matrix,intn){string newMatrix;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)newMatrix+=matrix[(n-1)*n+(i-1)-(j-1)*n];returnnewMatrix;}stringrotateCCW90(string matrix,intn){string newMatrix;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)newMatrix+=matrix[(n-1)-(i-1)+(j-1)*n];returnnewMatrix;}stringrotate180(string matrix){reverse(matrix.begin(),matrix.end());returnmatrix;}stringreflect(string matrix,intn){string newMatrix;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)newMatrix+=matrix[(n-i)*n+(j-1)];returnnewMatrix;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn,cases=0;while(cin>>n){cout<<"Pattern "<<++cases<<" was ";string original,transformed;charletter;for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){cin>>letter;original.push_back(letter);}for(intj=1;j<=n;j++){cin>>letter;transformed.push_back(letter);}}if(original==transformed){cout<<"preserved.\n";continue;}if(rotateCW90(original,n)==transformed){cout<<"rotated 90 degrees.\n";continue;}if(rotate180(original)==transformed){cout<<"rotated 180 degrees.\n";continue;}if(rotateCCW90(original,n)==transformed){cout<<"rotated 270 degrees.\n";continue;}original=reflect(original,n);if(original==transformed){cout<<"reflected vertically.\n";continue;}if(rotateCW90(original,n)==transformed){cout<<"reflected vertically and rotated 90 degrees.\n";continue;}if(rotate180(original)==transformed){cout<<"reflected vertically and rotated 180 degrees.\n";continue;}if(rotateCCW90(original,n)==transformed){cout<<"reflected vertically and rotated 270 degrees.\n";continue;}cout<<"improperly transformed.\n";}return0;}
