当前位置:首页 > 模拟 > 正文
SSOJ1071方块转换[USACO]
2540+

题目大意:两个n*n的图像A和B,有6种旋转方案,如果能实现A得到B,输出最小的方案编号,否则输出7。

题目描述

一块N x N(1<=N<=10)正方形的黑白瓦片的图案要被转换成新的正方形图案。写一个程序来找出将原始图案按照以下列转换方法转换成新图案的最小方式:

1:转90度:图案按顺时针转90度。

2:转180度:图案按顺时针转180度。

3:转270度:图案按顺时针转270度。

4:反射:图案在水平方向翻转(以中央铅垂线为中心形成原图案的镜像)。

5:组合:图案在水平方向翻转,然后再按照1到3之间的一种再次转换。

6:不改变:原图案不改变。

7:无效转换:无法用以上方法得到新图案。

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

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

输入

第一行: 单独的一个整数N。

第二行到第N+1行: N行每行N个字符(不是“@”就是“-”);这是转换前的正方形。

第N+2行到第2*N+1行: N行每行N个字符(不是“@”就是“-”);这是转换后的正方形。

输出

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

样例输入

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

样例输出

1

解题思路

依次找出旋转90°、180°、270°等的比较规律,对旋转后的和目标图像进行比较,如果有一个不相等,那么就是方案不可行,如果全都一样,那才说明方案可行。

如旋转90°,将原图各元素编号和新图各编号写下来,就可以找到规律:

31 21 11

32 22 12

33 23 13

新图的列号跟原来的行号i是一样的,行号与原来的列号之和等于n+1;其他角度也可以找出类似规律。

写出各个角度的判断函数,再写一个翻转函数,接下来就是分支嵌套,看先满足哪个方案就行。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,

SSOJ1071方块转换[USACO]:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!