洛谷P2630 图像变换题解

题意：

给定 $3$ 行 $3$ 列的图像各像素点灰度值，给定最终图像，求最短、字典序最小的操作序列。

其中，可能的操作及对应字符有如下四种：

A：顺时针旋转 $90$ 度；

B：逆时针旋转 $90$ 度；

C：左右翻转；

D：上下翻转。

输入格式：

一个矩阵，表示初始的图像。

一个矩阵，表示最终的图像。

输出格式：

最短、字典序最小的操作序列，保证长度不超过 $10^8$，不保证有解。

若长度不超过 $10^8$ 无解则输出 Poland cannot into space!!! 。

这种题目就是~~一眼暴搜~~。但是仔细观察可以发现有些操作其实是重复的

实际上一共只有 $8$ 种情况，否则无解

A  顺时针转 90° 
B  逆时针转 90°
C  左右翻转
D  上下翻转 = 左右翻转 + 转 180°
AA 转 180°
AB 不动
AC 左右翻转 + 顺时针转 90°
BC 左右翻转 + 逆时针转 180°

~~显然我一开始没发现这样的性质。~~

但是至少可以发现两次 C 和两次 D 是浪费

以及 A 和 B 都满足加起来不超过两次（他们不同时出现在答案序列中）

因此实际上这个答案序列最多 $4$ 。可以直接枚举所有情况。

当然如果你发现了只有 $8$ 种情况，那就更快呗。

时间复杂度 $O(1)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(15))
#define A {_A();}
#define B {_B();}
#define C {_C();}
#define D {_D();}
#define p(x) {if(ck()) return cout << x,0;}
int n=3,a[N][N],b[N][N],c[N][N];
bool ck()
{
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++)
		if(a[i][j] != b[i][j]) return 0;
	return 1;
}
void _B()
{
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) c[i][j] = a[j][n-i+1];
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) a[i][j] = c[i][j];
}
void _A() { _B(); _B(); _B(); }
void _C()
{ for(int i=1; i<=n; i++) for(int j=1; j<=n/2; j++) swap(a[i][j], a[i][n-j+1]); }
void _D() { _C(); _B(); _B(); } 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    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];
        p("AB")
    A   p("A")  B
    B   p("B")  A
    C   p("C")  C 
    D   p("D")  D
    A A p("AA") A A
    A C p("AC") C B
    B C p("BC")
    cout << "Poland cannot into space!!!" << '\n';
    return 0;
}