专栏文章

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

ddengrunze2608
P1205题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mip4txgn
此快照首次捕获于
2025/12/03 06:11
3 个月前
此快照最后确认于
2025/12/03 06:11
3 个月前
查看原文
相对较难的一道模拟题。
题目传送门

简述

要求我们判断给定的初始方块图案经过哪种变换后可以得到给出的目标图案，共有 77 种可能的变换情况：
  1. 进行 90°90\degree 旋转（顺时针）。
  2. 进行 180°180\degree 旋转（顺时针）。
  3. 进行 270°270\degree 旋转（顺时针）。
  4. 进行水平方向翻转（镜像）。
  5. 进行水平方向翻转后再进行某个旋转（组合）。
  6. 不做改变。
  7. 以上均不可行。

思路

创建 aa，bb，cc 三个二维数组，分别用于存储原图形，存储变换后的中间结果，存储目标结果。可以手写 66 个布尔类型函数，每个函数中用不同的变换方式把原图形进行变换后存储在 bb 数组中，与 cc 数组进行比对，相同返回 true，否则返回 false。具体解释如下：
假设原始图形为：
（1，1）（1，2）（1，3）
（2，1）（2，2）（2，3）
（3，1）（3，2）（3，3）
  1. 进行 90°90\degree 旋转的 work1：
（3，1）（2，1）（1，1）
（3，2）（2，2）（1，2）
（3，3）（2，3）（1，3）
原始行号 ii 变为 (n−i+1)(n-i+1)。
原始列号 jj 仍为 jj。
故新位置为 (j,n-i+1)，核心代码如下。
CPP
for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
        b[j][n-i+1]=a[i][j];
}
  1. 进行 180°180\degree 旋转的 work2：
（3，3）（3，2）（3，1）
（2，3）（2，2）（2，1）
（1，3）（1，2）（1，1）
原始行号 ii 变为 (n−i+1)(n-i+1)。
原始列号 jj 仍为 (n−j+1)(n-j+1)。
故新位置为 (n-i+1,n-j+1)，核心代码如下。
CPP
for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
        b[n-i+1][n-j+1]=a[i][j];
 }
  1. 进行 270°270\degree 旋转的 work3：
（1，3）（2，3）（3，3）
（1，2）（2，2）（3，2）
（1，1）（2，1）（3，1）
原始行号 ii 仍为 ii。
原始列号 jj 变为 (n−j+1)(n-j+1)。
故新位置为 (n-j+1,i)，核心代码如下。
CPP
for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
        b[n-j+1][i]=a[i][j];
}
  1. 进行水平方向翻转的 work4：
（1，3）（1，2）（1，1）
（2，3）（2，2）（2，1）
（3，3）（3，2）（3，1）
原始行号 ii 仍为 ii。
原始列号 jj 变为 (n−j+1)(n-j+1)。
故新位置为 (i,n-j+1)，核心代码如下。
CPP
for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
        b[i][n-j+1]=a[i][j];
}
  1. 进行水平方向翻转后再进行某个旋转的 work5：
先做一遍 work4，后从 work1 到 work3 都做一遍，每遍做完检查是否返回 true，返回了直接结束，未返回再运行下一个函数。
  1. 不做改变 work6：
直接检查即可。
最后再开一个 void⁡\operatorname{void} 类型函数，函数里面要从 work1⁡\operatorname{work1} 到 work6⁡\operatorname{work6} 先后执行这六个函数，如果发现那个函数返回了 true 则直接输出对应数字即可。如果前六个变换方法都返回 false，直接输出 77 表示均不可行即可。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
int n;
char a[15][15],b[15][15],c[15][15];
bool work1(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
        b[j][n-i+1]=a[i][j];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
        	if(b[i][j]!=c[i][j])
  	        return false;
  	    }    
	}
    return true;
}
bool work2(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
        b[n-i+1][n-j+1]=a[i][j];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
        	if(b[i][j]!=c[i][j])
       	    return false;
		}
     }
     return true;
}
bool work3(){
	for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
        b[n-j+1][i]=a[i][j];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
        	if(b[i][j]!=c[i][j])
        	return 0;
		}
    }
    return 1;
}
bool work4(){
	for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
        b[i][n-j+1]=a[i][j];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
        	if(b[i][j]!=c[i][j])
  			return false;
		}
    }
    return true;
}
bool work5(){
	work4();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			a[i][j]=b[i][j]; 
		}
	}   
    if(work1())return 1;
	   
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=n;j++)
        a[i][j]=b[i][j]; 
	}
    if(work2())return 1;
    
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=n;j++)
        a[i][j]=b[i][j]; 
	}
	if(work3())return 1;
	
    return false;
}
bool work6(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
       	    if(b[i][j]!=c[i][j])
            return 0;
	    }
    return 1;
}
void end(){
    if(work1()){
        cout<<1;
        return ;
    }
    if(work2()){
        cout<<2;
        return;
    }
    if(work3()){
    	cout<<3;
    	return;
	}
	if(work4()){
		cout<<4;
		return;
	}
	if(work5()){
		cout<<5;
		return;
	}
	if(work6()){
		cout<<6;
		return;
	}
	cout<<7;
}
signed main(){
    cin>>n;
    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>>c[i][j];
		}
	}
    end();
    return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...