像素混合

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file pixelshuffle.in Output file pixelshuffle.out

【题目描述】

在一个位图上进行像素混合有时会产生看似随机的图像。但在重复混合有限次后,总能恢复原始图像。这是意料之中的,因为“混合”意味着对位图上的像素执行一个一一对应的映射(或者叫置换)

你的程序被要求读入一个正整数n,和一系列的基本混合命令,定义了一个对n*n位图的像素混合序列φ。然后你的程序要计算出最小的数m(m>0),使n*n位图在执行m次混合序列φ后总能变成原来的图像。

例如,若φ是“逆时针旋转90°”,那么m=4.


【输入格式】

输入文件包含不超过10组数据。

输入文件的第一行是数据组数,第二行是空行。接下来分别给出了每组数据,两组数据之间有一个空行。

每组数据包含2行。

第1行是一个偶数n(2<=n<=2^10),表示位图的大小。我们用(i,j)描述位图上起第i行,左起第j列的像素。其中i,j从0开始。可以看到,左上角像素的坐标是(0,0)。

第2行是一个非空的混合命令序列,至多包含32个命令,命令之间由空格分隔。合法的命令是关键字"id","rot","sym","bhsym","bvsym","div","mix"之一,或者是它们中的某个后面加上"-"。每个关键字都描述了一种置换,如果后面加上"-",那就意味着该置换的逆置换。例如,"rot-"是逆时针旋转90°的逆置换,即顺时针旋转90°。最终,置换序列k1,k2,...,kp表示了总的置换φ=k1*k2*...*kp。例如,“bvsym rot-”对应的φ意味着将图像顺时针旋转90°,并且将图像的下半部分竖直翻转,如下图所示。

下面给出了各种关键字所对应的置换。

id:不变。

rot:逆时针旋转90°。

sym:水平翻转。置换后的(i,j)是原来的(i,n-1-j)。

bhsym:水平翻转图像的下半部分。置换后的(i,j)当i>=n/2时是原来的(i,n-1-j),其余情况则是(i,j)。

bvsym:竖直翻转图像的下半部分。

div:分割。第0,2,4,...,n-2行依次变成第0,1,...,n/2-1行;第1,3,...,n-1行依次变成第n/2,n/2+1,...,n-1行。

mix:行混合。将第2k和第2k+1行交错。第2k行的像素依次是原图的(2k,0),(2k+1,0),(2k,1),(2k+1,1),...,(2k,n/2-1,2k+1,n/2-1)。第2k+1行的像素依次是原图的(2k,n/2),(2k+1,n/2),(2k,n/2+1),(2k+1,n/2+1),...,(2k,n-1),(2k+1,n-1)。

下图给出了原图分别进行7种置换后的效果。

【输出格式】

对每组数据,输出题中要求的m,即使φ^m称为“不变”的最小m。数据保证m<2^31.

两组数据的输出之间用一个空行分隔。

【样例输入】

2

256

rot- div rot div

256

bvsym div mix

【样例输出】

8

63457

【来源】

UVa1156 Pixel Shuffle

刘汝佳,《算法竞赛入门经典训练指南》表2-10