1344. 转换

$USACO$ 题目

题目传送门

算法：找规律、二维数组下标技巧

除了直接翻转图案，还有什么更好的方法呢？

通过分析，我们还可以发现这题其实可以不用直接翻转图案，而是利用二维数组翻转后下标的规律。

首先，我们可以先开一个bool数组，用来表示前$6$种的转换方式是否可行。

如果前$6$种方法都不可行，就直接输出$7$。

那么，如何判断每种转换方式是否可行呢？

我们可以遍历二维数组$b$（新图案）中的每一个字符，判断这个字符转换后的位置是否与二维数组$a$当前位置的字符相同，若不相同直接将该转换方式标记为true（不可行）

下面是前$6$种转换方式的规律：

1. $90$ 度旋转：将图案顺时针旋转 $90$ 度。

通过找规律发现,i,j旋转 $90$ 度后下标变为j,n-i+1

所以a[i][j]->a[j][n-i+1]

2. $180$ 度旋转：将图案顺时针旋转 $180$ 度。

旋转 $180$ 度就相当于旋转2次 $90$ 度，第1次旋转为j,n-i+1,那么第2次旋转就是n-i+1,n-j+1

所以a[i][j]->a[n-i+1][n-j+1]

3. $270$ 度旋转：将图案顺时针旋转 $270$ 度。

同理，旋转 $270$ 度相当于旋转3次 $90$ 度，那么第3次旋转就是n-j+1,n-(n-j+1)+1

所以a[i][j]->a[n-j+1][n-(n-j+1)+1

4.镜像：沿着图片的中间垂直线翻转图片，使其变为自身的镜像。

这里需要注意的是，题目指的是左右翻转，而不是上下翻转

由于是左右翻转，i肯定是不会变的，因为左右翻转后肯定还是在那一行，只是改变了列。j改变的规律也很好找，规律就是原来该元素是在左数第几个位置，那么翻转后它的位置就是在右数第几个位置，从而得出j变为n-j+1

所以a[i][j]->a[i][n-j+1]

5.组合：先进行镜像转换，再按照1∼3中的一种方式进行转换。

这种操作比较麻烦，因为镜像转换后还有有3种可能：操作1，操作2，操作3

那么我们可以分情况讨论，先开设一个新的bool数组，分别表示操作1，操作2，操作3是否可行。到最后再判断一下，如果三种可能都不可行，就代表操作5不可行

我们先把操作4的规律写下来，再按照前面1~3操作的方式得出规律

所以3种可能的规律分别是a[i][j]->a[n-j+1][n-i+1],a[i][j]->a[n-i+1][n-(n-j+1)+1],a[i][j]->a[n-(n-j+1)+1][n-(n-i+1)+1]

6.不改变：保持原图案，不做任何改变。

这种操作就非常简单了，位置不作任何改变

所以，a[i][j]->a[i][j]

最后，把所有的规律整合起来，就可以写出代码了

c++代码

#include<bits/stdc++.h>
using namespace std;
int n;
char a[20][20],b[20][20];
bool r[17],r5[13];
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) cin>>a[i][j];
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) cin>>b[i][j];
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(b[j][n-i+1]!=a[i][j]) r[1]=true;
            if(b[n-i+1][n-j+1]!=a[i][j]) r[2]=true;
            if(b[n-j+1][n-(n-i+1)+1]!=a[i][j]) r[3]=true;
            if(b[i][n-j+1]!=a[i][j]) r[4]=true;
            if(b[n-j+1][n-i+1]!=a[i][j]) r5[1]=true;
            if(b[n-i+1][n-(n-j+1)+1]!=a[i][j]) r5[2]=true;
            if(b[n-(n-j+1)+1][n-(n-i+1)+1]!=a[i][j]) r5[3]=true;
            if(b[i][j]!=a[i][j]) r[6]=true;
        }
    }
    if(r5[1]&&r5[2]&&r5[3]) r[5]=true;
    for(int i=1; i<=6; i++) {
        if(!r[i]) {
            printf("%d",i);
            return 0;
        }
    }
    printf("7");
    return 0;
}