【深基5.习11】[USACO1.2] 方块转换 Transformations

解题思路

实现顺时针旋转与左右镜像函数。按编号 1～6 的优先级依次比较目标图案，首个匹配立即输出；都不匹配输出 7。

正确性说明

旋转映射 (i,j)→(j,n-1-i) 正确转 90 度；镜像映射 (i,j)→(i,n-1-j) 正确翻转。枚举全部允许变换并按编号检查，得到最小可用编号。

易错点

组合是先镜像再旋转，不是转置；不改变的优先级在组合之后。

复杂度

时间 O(n²)，空间 O(n²)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

vector<string> rot(const vector<string> &a) {
    int n = a.size();
    vector<string> b(n, string(n, ' '));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            b[j][n - 1 - i] = a[i][j];
    return b;
}
vector<string> mirror(vector<string> a) {
    for (string &s : a)
        reverse(s.begin(), s.end());
    return a;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<string> a(n), b(n);
    for (string &s : a)
        cin >> s;
    for (string &s : b)
        cin >> s;
    auto t = a;
    for (int k = 1; k <= 3; k++) {
        t = rot(t);
        if (t == b) {
            cout << k << "\n";
            return 0;
        }
    }
    t = mirror(a);
    if (t == b) {
        cout << 4 << "\n";
        return 0;
    }
    for (int k = 1; k <= 3; k++) {
        t = rot(t);
        if (t == b) {
            cout << 5 << "\n";
            return 0;
        }
    }
    cout << (a == b ? 6 : 7) << "\n";
    return 0;
}