CF958A1 Death Stars (easy) 解题报告

题目传送门

题目大意

给出两张只含有 X 和 O 的表，问是否能通过旋转和翻转把其中一个变为另一个。

解题思路

这题一看就是一道大水题！！！

算法：模拟所有情况。

首先我们先画出一张简单的表模拟一下（设两张表分别为 \(A\) 和 \(B\)）：

初始的 \(A\)：

\(A\)	\(B\)
\(C\)	\(D\)

这里一共有 \(8\) 种对 \(A\) 操作后的表：

顺时针：\(ABCD\)（四种）

逆时针：\(DCBA\)（四种）

Details:

1. 不进行改变

\(A\)	\(B\)
\(C\)	\(D\)

对应布尔判断式 \(A_{i,j}=B_{i,j}\)（\(A\) 操作后对应 \(B\) 的位置）；

2. 竖直翻转一次

\(C\)	\(D\)
\(A\)	\(B\)

对应布尔判断式 \(A_{i,j}=B_{n-i+1,j}\)；

3. 水平翻转一次

\(B\)	\(A\)
\(D\)	\(C\)

对应布尔判断式 \(A_{i,j}=B_{i,n-j+1}\)；

4. 水平翻转一次再竖直翻转一次

\(D\)	\(C\)
\(B\)	\(A\)

对应布尔判断式 \(A_{i,j}=B_{n-i+1,n-j+1}\)；

5. 左旋 \(90^{\circ}\) 再竖直翻转一次

\(A\)	\(C\)
\(B\)	\(D\)

对应布尔判断式 \(A_{i,j}=B_{j,i}\)；

6. 左旋 \(90^{\circ}\) 再竖直翻转一次再竖直翻转一次

\(B\)	\(D\)
\(A\)	\(C\)

对应布尔判断式 \(A_{i,j}=B_{n-j+1,i}\)；

7. 左旋 \(90^{\circ}\) 再竖直翻转一次再水平翻转一次

\(C\)	\(A\)
\(D\)	\(B\)

对应布尔判断式 \(A_{i,j}=B_{j,n-i+1}\)；

8. 左旋 \(90^{\circ}\) 再竖直翻转一次再水平翻转一次再竖直翻转一次

\(D\)	\(B\)
\(C\)	\(A\)

对应布尔判断式 \(A_{i,j}=B_{n-j+1,n-i+1}\)。

经证明，其他所有翻转旋转情况都是这 \(8\) 种情况的任意一种。

AC Code

#include<iostream>
#include<cstdio>
#define N 12
using namespace std;
int n,flag;
char A[N][N],B[N][N];
signed main()
{cin>>n;for(int i=1;i<=n;i++)cin>>(A[i]+1);for(int i=1;i<=n;i++)cin>>(B[i]+1);flag=1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(A[i][j]!=B[i][j])//枚举每一种 flag=0;if(flag)puts("Yes"),exit(0);//某种情况符合直接输出 Yes，然后结束程序 flag=1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(A[i][j]!=B[n-i+1][j])flag=0;if(flag)puts("Yes"),exit(0);flag=1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(A[i][j]!=B[i][n-j+1])flag=0;if(flag)puts("Yes"),exit(0);flag=1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(A[i][j]!=B[n-i+1][n-j+1])flag=0;if(flag)puts("Yes"),exit(0);flag=1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(A[i][j]!=B[j][i])flag=0;if(flag)puts("Yes"),exit(0);flag=1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(A[i][j]!=B[n-j+1][i])flag=0;if(flag)puts("Yes"),exit(0);flag=1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(A[i][j]!=B[j][n-i+1])flag=0;if(flag)puts("Yes"),exit(0);flag=1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(A[i][j]!=B[n-j+1][n-i+1])flag=0;if(flag)puts("Yes"),exit(0);puts("No");//都不符合，输出 No  return 0;
}

屎山代码有点难看，不过还是通俗易懂的吧。