[USACO1.2] 方块转换 Transformations 题目解析

洛谷P1205 [USACO1.2] 方块转换 Transformations 题目解析

题目描述

一块 n × n n \times n n×n 正方形的黑白瓦片的图案要被转换成新的正方形图案。写一个程序来找出将原始图案按照以下列转换方法转换成新图案的最小方式：

• 转 90 ° 90\degree 90°：图案按顺时针转 90 ° 90\degree 90°。

• 转 180 ° 180\degree 180°：图案按顺时针转 180 ° 180\degree 180°。

• 转 270 ° 270\degree 270°：图案按顺时针转 270 ° 270\degree 270°。

• 反射：图案在水平方向翻转（以中央铅垂线为中心形成原图案的镜像）。

• 组合：图案在水平方向翻转，然后再按照 1 ∼ 3 1 \sim 3 1∼3 之间的一种再次转换。

• 不改变：原图案不改变。

• 无效转换：无法用以上方法得到新图案。

如果有多种可用的转换方法，请选择序号最小的那个。

只使用上述 7 7 7 个中的一个步骤来完成这次转换。

输入格式

第一行一个正整数 n n n。

然后 n n n 行，每行 n n n 个字符，全部为 @ 或 -，表示初始的正方形。

接下来 n n n 行，每行 n n n 个字符，全部为 @ 或 -，表示最终的正方形。

输出格式

单独的一行包括 1 ∼ 7 1 \sim 7 1∼7 之间的一个数字（在上文已描述）表明需要将转换前的正方形变为转换后的正方形的转换方法。

样例 #1

样例输入 #1

3
@-@
---
@@-
@-@
@--
--@

样例输出 #1

1

提示

【数据范围】
对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 10 1\le n \le 10 1≤n≤10。

题目翻译来自 NOCOW。

USACO Training Section 1.2

解析：

有点恶心的模拟题，利用函数实现转换操作，然后判断哪个方案能够转换成新图案，解决步骤如下：

1. 实现转换函数：

• 90 90 90 度顺时针旋转，代码中 t u r n 90 ( ) turn90() turn90() 函数

• 180 180 180 度顺时针旋转，代码中 t u r n 180 ( ) turn180() turn180() 函数

• 270 270 270 度顺时针旋转，代码中 t u r n 270 ( ) turn270() turn270() 函数

• 水平翻转，代码中 f a n s h e ( ) fanshe() fanshe() 函数

2. 检查图案：比较转换后的图案与目标图案是否相同，代码中 c h e c k ( ) check() check() 函数

3. 输出结果：根据可行的转换操作输出最小的转换编号

代码如下：

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

char in[15][15],tmp[15][15],tmp1[15][15],ans[15][15];
int n;

bool check(char ch1[][15],char ch2[][15]) { //判断转换后图案与目标图案是否相同
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			if(ch1[i][j]!=ch2[i][j]) return 0;
		}
	}
	return 1;
}

void turn90(char ch1[][15],char ch2[][15]) { //顺时针转 90 度
	for(int j=0;j<n;j++) {
		for(int i=n-1;i>=0;i--) {
			ch2[j][n-i-1] = ch1[i][j];
		}
	}
}

void turn180(char ch1[][15],char ch2[][15]) { //顺时针转 180 度
	for(int i=n-1;i>=0;i--) {
		for(int j=n-1;j>=0;j--) {
			ch2[n-i-1][n-j-1] = ch1[i][j];
		}
	} 
}

void turn270(char ch1[][15],char ch2[][15]) { //顺时针转 270 度
	for(int j=n-1;j>=0;j--) {
		for(int i=0;i<n;i++) {
			ch2[n-j-1][i] = ch1[i][j];
		}
	}
}

void fanshe(char ch1[][15],char ch2[][15]) { // 反射操作
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			ch2[i][n-j-1] = ch1[i][j];
		}
	}
}

int main() {
	cin>>n;
	for(int i=0;i<n;i++) cin>>in[i];
	for(int i=0;i<n;i++) cin>>ans[i];
	turn90(in,tmp);
	if(check(tmp,ans)) { //判断 1 操作
		cout<<1<<endl;
		return 0;
	}
	turn180(in,tmp);
	if(check(tmp,ans)) { //判断 2 操作
		cout<<2<<endl;
		return 0;
	}
	turn270(in,tmp);
	if(check(tmp,ans)) { //判断 3 操作
		cout<<3<<endl;
		return 0;
	}
	fanshe(in,tmp);
	if(check(tmp,ans)) { //判断 4 操作
		cout<<4<<endl;
		return 0;
	}
	bool flag; //判断 5 操作
	turn90(tmp,tmp1);
	flag = check(tmp1,ans);
	turn180(tmp,tmp1);
	flag = flag || check(tmp1,ans);
	turn270(tmp,tmp1);
	flag = flag || check(tmp1,ans);
	if(flag) {
		cout<<5<<endl;
		return 0;
	}
	if(check(in,ans)) { //判断 6 操作
		cout<<6<<endl;
		return 0;
	}
	cout<<7<<endl; //都不满足，输出 7
	return 0;
} 

由于每个转换操作和比较都需要遍历 n × n n \times n n×n 的数组，因此总体复杂度为 O ( n 2 ) O(n^2) O(n2)。