题解 P1205 【[USACO1.2]方块转换 Transformations】
Creeper_LKF
2017-07-02 14:29:43
###常数级的优化
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
char matrix_s[10][10],matrix_t[10][10];//起始矩阵和目标矩阵
int n,could=8;
bool ways[5]={true,true,true,true,true},way1=true,way2=true,way3=true;//记录各种可能状态,如果发现都不行则结束程序
scanf("%d",&n);//感谢楼下提醒,似乎有些题目真的不能用getchar(可能是数据后多接了几个空格吧,如果非要用,那么最好用
for(int i=0;i<n;i++){//while循环来吃空格换行符)
scanf("\n");
for(int j=0;j<n;j++){
scanf("%c",&matrix_s[i][j]);
}
}
for(int i=0;i<n;i++){
scanf("\n");
for(int j=0;j<n;j++){
scanf("%c",&matrix_t[i][j]);
}
}
for(int i=0;i<n;i++){//只要枚举一次矩阵就行了
for(int j=0;j<n;j++){
if(!could){
printf("7");
return 0;
}
if(ways[0]&&matrix_s[i][j]!=matrix_t[j][n-i-1]) ways[0]=false,could--;//可以打草稿列出来
if(ways[1]&&matrix_s[i][j]!=matrix_t[n-i-1][n-j-1]) ways[1]=false,could--;
if(ways[2]&&matrix_s[i][j]!=matrix_t[n-j-1][i]) ways[2]=false,could--;
if(ways[3]&&matrix_s[i][j]!=matrix_t[i][n-j-1]) ways[3]=false,could--;
if(ways[5]&&matrix_s[i][j]!=matrix_t[i][j]) ways[5]=false,could--;
if(way1&&matrix_s[i][j]!=matrix_t[n-j-1][n-i-1]) way1=false,could--;
if(way2&&matrix_s[i][j]!=matrix_t[n-i-1][j]) way2=false,could--;//当镜像时90°和270°并不简单地等价
if(way3&&matrix_s[i][j]!=matrix_t[j][i]) way3=false,could--;//画图思考
if(!(way1||way2||way3)) ways[4]=false;//注意逻辑关系
}
}
for(int i=0;i<6;i++){
if(ways[i]){
printf("%d",i+1);//输出的序号要比数组下标大1
return 0;
}
}
printf("7");//如果最后一个点使could=0,那么上面将无法输出7
return 0;
}
```