P1205 方块转换 Transformations【洛谷算法习题】
P1205 方块转换 Transformations
网页链接
P1205 方块转换 Transformations
题目描述
一块n × n n \times nn×n正方形的黑白瓦片的图案要被转换成新的正方形图案。写一个程序来找出将原始图案按照以下列转换方法转换成新图案的最小方式：
转90 ° 90\degree90°：图案按顺时针转90 ° 90\degree90°。
转180 ° 180\degree180°：图案按顺时针转180 ° 180\degree180°。
转270 ° 270\degree270°：图案按顺时针转270 ° 270\degree270°。
反射：图案在水平方向翻转（以中央铅垂线为中心形成原图案的镜像）。
组合：图案在水平方向翻转，然后再按照1 ∼ 3 1 \sim 31∼3之间的一种再次转换。
不改变：原图案不改变。
无效转换：无法用以上方法得到新图案。
如果有多种可用的转换方法，请选择序号最小的那个。
只使用上述7 77个中的一个步骤来完成这次转换。
输入格式
第一行一个正整数n nn。
然后n nn行，每行n nn个字符，全部为@或-，表示初始的正方形。
接下来n nn行，每行n nn个字符，全部为@或-，表示最终的正方形。
输出格式
单独的一行包括1 ∼ 7 1 \sim 71∼7之间的一个数字（在上文已描述）表明需要将转换前的正方形变为转换后的正方形的转换方法。
输入输出样例 #1
输入 #1
3 @-@ --- @@- @-@ @-- --@输出 #1
1说明/提示
【数据范围】
对于100 % 100\%100%的数据，1 ≤ n ≤ 10 1\le n \le 101≤n≤10。
题目翻译来自 NOCOW。
USACO Training Section 1.2
解题思路
本题核心是矩阵变换模拟+按优先级校验，严格按照题目要求的转换序号顺序判断最优解。首先实现两个基础变换函数：顺时针旋转90度、水平镜像翻转，180度/270度旋转通过重复调用旋转函数实现，组合变换为翻转后叠加旋转。按照序号1→2→3→4→5→6的优先级，依次对原始矩阵执行对应变换，每变换一次就与目标矩阵比对，一旦匹配立即输出对应序号；若所有变换都不匹配，输出7代表无效转换。由于数据规模n ≤ 10 n≤10n≤10，暴力模拟变换过程简洁高效，完全满足题目要求。
总结
核心逻辑：按题目指定的序号优先级，模拟所有合法矩阵变换，逐一匹配目标矩阵。
关键操作：实现旋转、翻转基础变换，按序校验匹配结果。
效率保障：小数据暴力模拟，代码简洁直观，严格遵循题目规则。
代码内容
#include<iostream>#include<vector>#include<string>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll p=1e9+7;constll INF=1e18;constll M=1e6+10;typedefvector<string>G;Gr90(constG&g){intn=g.size();Gr(n,string(n,' '));for(inti=0;i<n;++i)for(intj=0;j<n;++j)r[j][n-1-i]=g[i][j];returnr;}Gref(constG&g){intn=g.size();G r=g;for(inti=0;i<n;++i)for(intj=0;j<n/2;++j)swap(r[i][j],r[i][n-1-j]);returnr;}booleq(constG&a,constG&b){intn=a.size();for(inti=0;i<n;++i)for(intj=0;j<n;++j)if(a[i][j]!=b[i][j])returnfalse;returntrue;}intmain(){intn;cin>>n;Ga(n),b(n);for(inti=0;i<n;++i)cin>>a[i];for(inti=0;i<n;++i)cin>>b[i];G r=a;for(inti=1;i<=3;++i){r=r90(r);if(eq(r,b)){cout<<i<<endl;return0;}}G rf=ref(a);if(eq(rf,b)){cout<<4<<endl;return0;}r=rf;for(inti=1;i<=3;++i){r=r90(r);if(eq(r,b)){cout<<5<<endl;return0;}}if(eq(a,b)){cout<<6<<endl;return0;}cout<<7<<endl;return0;}