[USACO1.2] 方块转换 Transformations

洛谷·深入浅出 · 代码 · cpp · 难度 4/5 · 共 1499 字

判断方块从初始到目标的最小变换（1-7）

洛谷
练习

正文

// 原题：https://oj.yecheng.tv/p/1413
// 题意：n×n 的 @/- 图案变成新图案，求最小变换编号：1=转90 2=转180 3=转270 4=水平镜像 5=镜像后再转1-3 6=不变 7=无效。
// 思路：实现旋转/镜像，依次尝试 1,2,3,4,(4再做1/2/3),6，命中即输出，否则 7。
// 复杂度：O(n^2)。
// 易错点：优先级取最小；5 是镜像后接旋转 90/180/270 之一。
#include <iostream>
using namespace std;
int n;
char a[12][12], b[12][12], t[12][12], r[12][12];
void rotate90(char s[12][12], char d[12][12]){
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) d[j][n - 1 - i] = s[i][j];
}
void reflect(char s[12][12], char d[12][12]){
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) d[i][n - 1 - j] = s[i][j];
}
bool same(char s[12][12], char d[12][12]){
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) if(s[i][j] != d[i][j]) return false;
    return true;
}
int main(){
    cin >> n;
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin >> a[i][j];
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin >> b[i][j];
    rotate90(a, t); if(same(t, b)){ cout << 1 << endl; return 0; }
    rotate90(t, r); if(same(r, b)){ cout << 2 << endl; return 0; }
    rotate90(r, t); if(same(t, b)){ cout << 3 << endl; return 0; }
    reflect(a, t); if(same(t, b)){ cout << 4 << endl; return 0; }
    rotate90(t, r); if(same(r, b)){ cout << 5 << endl; return 0; }
    rotate90(r, t); if(same(t, b)){ cout << 5 << endl; return 0; }
    rotate90(t, r); if(same(r, b)){ cout << 5 << endl; return 0; }
    if(same(a, b)){ cout << 6 << endl; return 0; }
    cout << 7 << endl;
    return 0;
}

[USACO1.2] 方块转换 Transformations

正文

洛谷·深入浅出的其它内容