UVa 466 Mirror Mirror

题目描述题目要求识别给定正方形图案经过的变换。可能的变换有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度。若图案可通过多种变换得到输出工作量最小的那个。输入格式输入包含多个图案数据集。每个数据集第一行为整数nnn1≤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×ncr \times n cr×nc新索引为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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;stringrotateCW90(string matrix,intn){string newMatrix;for(inti1;in;i)for(intj1;jn;j)newMatrixmatrix[(n-1)*n(i-1)-(j-1)*n];returnnewMatrix;}stringrotateCCW90(string matrix,intn){string newMatrix;for(inti1;in;i)for(intj1;jn;j)newMatrixmatrix[(n-1)-(i-1)(j-1)*n];returnnewMatrix;}stringrotate180(string matrix){reverse(matrix.begin(),matrix.end());returnmatrix;}stringreflect(string matrix,intn){string newMatrix;for(inti1;in;i)for(intj1;jn;j)newMatrixmatrix[(n-i)*n(j-1)];returnnewMatrix;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn,cases0;while(cinn){coutPattern cases was ;string original,transformed;charletter;for(inti1;in;i){for(intj1;jn;j){cinletter;original.push_back(letter);}for(intj1;jn;j){cinletter;transformed.push_back(letter);}}if(originaltransformed){coutpreserved.\n;continue;}if(rotateCW90(original,n)transformed){coutrotated 90 degrees.\n;continue;}if(rotate180(original)transformed){coutrotated 180 degrees.\n;continue;}if(rotateCCW90(original,n)transformed){coutrotated 270 degrees.\n;continue;}originalreflect(original,n);if(originaltransformed){coutreflected vertically.\n;continue;}if(rotateCW90(original,n)transformed){coutreflected vertically and rotated 90 degrees.\n;continue;}if(rotate180(original)transformed){coutreflected vertically and rotated 180 degrees.\n;continue;}if(rotateCCW90(original,n)transformed){coutreflected vertically and rotated 270 degrees.\n;continue;}coutimproperly transformed.\n;}return0;}