题解 P2630 【图像变换】

· · 题解

说句实话，我一看到这题目时确实被吓得不浅，不过窝睡了一晚上后突然灵感冒出（想了一晚上就直说），终于 AC 了，一看还能交题解，而且偶跟别人做法也不同，所以就来一篇题解吧。

首先理清一下思路，题目说： 

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

这个 10^{8} 吓人不浅，但是，只要仔细打一下草稿，就会发现，其实就一共 9 种情况： 

A（顺时针转 90 度）
B（逆时针转 90 度）
C（左右翻转）
D（上下翻转，也可以理解成左右翻转后再转 180 度）
AA（转 180 度）
AB（不动）
AC（左右翻转并顺时针转 90 度）
BC（左右翻转并逆时针转 90 度）
最后一种是无解。

有人会问：上下翻转为什么珂以理解成左右翻转后再转 180 度？这其实就是一块玻璃，怎么翻转还是只有两面，转完两面后就转 180 度其实就是上下翻转了= =（自己推算的不确定）

既然只有九种情况，那么就好办了。

第一种情况A：B+B+B

第二种情况B： 

for (int i=1; i<=n; i++)
    for (int j=1; j<=n; j++) {
        int x = j;
        int y = n - i + 1;//这种东西在草稿纸上画两下数对，然后就珂以很容易理解了
        c[i][j] = a[x][y];
    }
for (int i=1; i<=n; i++)
    for (int j=1; j<=n; j++)
        a[i][j] = c[i][j];

第三种情况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]);

第四种D就直接为：C+B+B

剩下四种都是组合，就不需要解释了，下面给个有注释的代码： 

#include<bits/stdc++.h>
#define endl '\n'
#pragma GCC optimize(3)

using namespace std;
int a[10][10], b[10][10], c[10][10];
const int n = 3;

inline bool judgement()//这个是判断 a 和 b 相不相等的函数 
{
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            if (a[i][j] != b[i][j])
                return false;
    return true;
}

inline void B() {//偶打了个 B 先 
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++) {
            int x = j;
            int y = n - i + 1;
            c[i][j] = a[x][y];
        }
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            a[i][j] = c[i][j];
}

inline void A() { B(); B(); B(); } //用一个函数，主程序好打很多 

inline void C() {//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]);
}

inline void D() { C(); B(); B(); } 

signed main() {
    ios::sync_with_stdio(false);
    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];//输入 
    if (judgement()) return cout << "AB", 0;//不变的先判断了再说（
    A();
    if (judgement()) return cout << "A", 0;//A的情况 
    B(); /*因为需要把它变回原来的形状才行，逆时针可以把顺时针弄回去，下面的道理相同*/B();
    if (judgement()) return cout << "B", 0;
    A(); C();
    if (judgement()) return cout << "C", 0;
    C();/*C 的翻转就是再把 C 翻转一次*/ D();
    if (judgement()) return cout << "D", 0;
    D(); A(); A();
    if (judgement()) return cout << "AA", 0;
    A(); A(); A(); C();
    if (judgement()) return cout << "AC", 0;
    C(); B(); B(); C();
    if (judgement()) return cout << "BC", 0;
    cout << "Poland cannot into space!!!";
    return 0;//被大佬嫌弃不加 return 0; ，这次加上（
}

如果有不懂，珂以找这个菜鸡私信解答qwq。