专栏文章

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

ggodDDY
P1205题解参与者 13已保存评论 14

文章操作

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

当前评论
13 条
当前快照
1 份
快照标识符
@mip3j696
此快照首次捕获于
2025/12/03 05:34
3 个月前
此快照最后确认于
2025/12/03 05:34
3 个月前
查看原文

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

题目传送门

比较经典的一类模拟题。这道模拟题有些难度的，但很好理解。
题目大意就是给你一个初始字符矩阵和一个目标字符矩阵，让你用题目给出的几种方法将初始矩阵转化成目标矩阵。

方法概述

  • 方法 1：将初始矩阵顺时针旋转 90°90°（核心转换方法）。
  • 方法 2：将初始矩阵顺时针旋转 180°180°（重复两遍方法一）。
  • 方法 3：将初始矩阵顺时针旋转 270°270°（三遍方法一）。
  • 方法 4：将初始矩阵左右翻转（核心转换方法）。
  • 方法 5：先左右翻转，再使用方法 1∼31 \sim 3 中的一种。
  • 方法 6：保持原矩阵不变。
  • 方法 7：使用以上方法都不能得到目标矩阵。
看似有七种转换方法，但其实后两种就是无用的干扰项。

思路

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

顺时针旋转

让我们来画个图吧！
根据图片可以发现，在经过方法一后，位置有以下变化：
发现规律了吧！在旋转后的新数组中，数对的后项 kk 是列、从大到小，前项 jj 是行、从小到大。
那么，由此规律，可以推导出这个双重 for 循环：
CPP
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];
    	}
	}
}

左右翻转

一样的，先来画个图。
画图后，位置变化规律就很显而易见了：
很明显吧！在同一行中，两个指针从两边开始往中间靠，交换一下位置就是翻转后的矩阵了！那代码也出来了：
CPP
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 :
CPP
#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;
	//完结撒花 
}

警钟

  1. 在 main 函数里，每次操作完后一定要初始化，不然会错的很惨（别问我怎么知道的）。
  2. 可能有多种方法可以正确转换，但只输出编号最小的那一个方法！
蒟蒻的第一篇题解，图画的有点丑请见谅。
管理员大大求过！

评论

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

正在加载评论...