题解：P1205 [USACO1.2] 方块转换 Transformations

godDDY · 2025-06-13 17:56:25 · 题解

P1205 [USACO1.2] 方块转换题解

题目传送门

比较经典的一类模拟题。这道模拟题有些难度的，但很好理解。

题目大意就是给你一个初始字符矩阵和一个目标字符矩阵，让你用题目给出的几种方法将初始矩阵转化成目标矩阵。

方法概述

方法 1：将初始矩阵顺时针旋转 90°（核心转换方法）。
方法 2：将初始矩阵顺时针旋转 180°（重复两遍方法一）。
方法 3：将初始矩阵顺时针旋转 270°（三遍方法一）。
方法 4：将初始矩阵左右翻转（核心转换方法）。
方法 5：先左右翻转，再使用方法 1 \sim 3 中的一种。
方法 6：保持原矩阵不变。
方法 7：使用以上方法都不能得到目标矩阵。

看似有七种转换方法，但其实后两种就是无用的干扰项。

思路

Q ：一看到图形题，先想到什么？
A ：~~瞪眼法~~画图找规律！

顺时针旋转

让我们来画个图吧！

根据图片可以发现，在经过方法一后，位置有以下变化：

发现规律了吧！在旋转后的新数组中，数对的后项 k 是列、从大到小，前项 j 是行、从小到大。
那么，由此规律，可以推导出这个双重 for 循环：

void turn90(){
    for(int i=0,k=n-1;i<n,k>=0;i++,k--){ //i是原矩阵的行，k是新矩阵的列 
        for(int j=0;j<n;j++){ //因为原矩阵的列和新矩阵的行变化一样，所以可以共用j 
            now[j][k]=old[i][j];
        }
    }
}

左右翻转

一样的，先来画个图。

画图后，位置变化规律就很显而易见了：

很明显吧！在同一行中，两个指针从两边开始往中间靠，交换一下位置就是翻转后的矩阵了！那代码也出来了：

void revers(){
    for(int i=0;i<n;i++){ //左右翻转是逐行进行的 
        for(int j=0,k=n-1;j<=k;j++,k--){ //用两个指针从两边往中间走，能省去一半的时间 
            now[i][j]=old[i][k];
            now[i][k]=old[i][j]; //新矩阵和原矩阵相反 
        }
    }
}

代码

其它方法都是以这两种为基础来操作的，所以这两种方法的代码有了，那其它的代码自然地就出来了！

AC code :

#include<bits/stdc++.h>
using namespace std;
int n;
char _stat[15][15],old[15][15],now[15][15],_end[15][15];
//初始化矩阵、操作的原矩阵、操作的新矩阵和目标矩阵
//注意，操作时是用old矩阵和now矩阵，不能改变_stat矩阵 
void in(){ //输入函数 
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>_stat[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>_end[i][j];
        }
    }
}
void f(){ //初始化函数 
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            now[i][j]=old[i][j]=_stat[i][j];
        }
    }
}
bool check(){ //判断操作后的新矩阵与目标矩阵是否符合 
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            if(now[i][j]!=_end[i][j])
                return false;
    }
    return true;
}
void turn90(){ //顺时针旋转90° 
    for(int i=0,k=n-1;i<n;i++,k--){
        for(int j=0;j<n;j++){
            now[j][k]=old[i][j];
        }
    }
    for(int i=0;i<n;i++){ //更新原矩阵 
        for(int j=0;j<n;j++){
            old[i][j]=now[i][j];
        }
    }
}
void revers(){ //左右翻转 
    for(int i=0;i<n;i++){
        for(int j=0,k=n-1;j<=k;j++,k--){
            now[i][j]=old[i][k];
            now[i][k]=old[i][j];
        }
    }
    for(int i=0;i<n;i++){ //更新原矩阵 
        for(int j=0;j<n;j++){
            old[i][j]=now[i][j];
        }
    }
}
void turn180(){ //顺时针旋转180° 
    turn90();
    turn90();
}
void turn270(){ //顺时针旋转270° 
    turn180();
    turn90();
}
bool comb(){ //组合方法 
    revers(); //先反转 
    turn90(); //选择转90°的情况 
    if(check()) return true; //判断与目标矩阵是否符合 
    f(); //初始化 

    revers();
    turn180(); //选择转180°的情况 
    if(check()) return true;
    f();

    revers();
    turn270(); //选择转270°的情况 
    if(check()) return true;
    f();

    return false; //如果都不行就返回false 
}
int main(){
    cin>>n;
    in();
    f(); //初始化 
    turn90(); //方法1是否可行 
    if(check()){
        cout<<1;
        return 0;
    }
    f(); //每次使用玩方法后都要初始化！一定注意！ 

    turn180(); //法2可行性 
    if(check()){
        cout<<2;
        return 0;
    }
    f();

    turn270(); //法3可行性 
    if(check()){
        cout<<3;
        return 0;
    }
    f();

    revers(); //法4可行性 
    if(check()){
        cout<<4;
        return 0;
    }
    f();

    if(comb()){ //法5可行性 
        cout<<5;
        return 0;
    }
    f();

    if(check()){ //不改变原矩阵，直接check 
        cout<<6;
        return 0;
    }
    cout<<7; //前6种方法都不行就输出7 
    return 0;
    //完结撒花 
}

警钟

在 main 函数里，每次操作完后一定要初始化，不然会错的很惨（别问我怎么知道的）。
可能有多种方法可以正确转换，但只输出编号最小的那一个方法！

蒟蒻的第一篇题解，图画的有点丑请见谅。
管理员大大求过！