SPOJ JPIX Pixel Shuffle_综合

Shuffling the pixels in a bitmap image sometimes yields random looking
images. However, by repeating the shuffling enough times, one finally
recovers the original images. This should be no surprise, since
“shuffling” means applying a one-to-one mapping (or permutation) over
the cells of the image, which come in finite number.

Your program should read a number n , and a series of elementary
transformations that define a “shuffling” of n * n images. Then, your
program should compute the minimal number m (m > 0) , such that m
applications of always yield the original n * n image.

For instance if is counter-clockwise 90o rotation then m = 4.

Input

Test cases are given one after another, and a single 0 denotes the end
of the input. For each test case:

Input is made of two lines, the first line is number n (2 <= n <= 210
, n even). The number n is the size of images, one image is
represented internally by a n * n pixel matrix (aji) , where i is the
row number and j is the column number. The pixel at the upper left
corner is at row 0 and column 0.

The second line is a non-empty list of at most 32 words, separated by
spaces. Valid words are the keywords id, rot, sym, bhsym, bvsym, div
and mix, or a keyword followed by -. Each keyword key designates an
elementary transform (as defined by Figure 1), and key- designates the
inverse of transform key. For instance, rot- is the inverse of
counter-clockwise 90o rotation, that is clockwise 90o rotation.
Finally, the list k1, k2, …, kp designates the compound transform =
k1ok2o … okp . For instance, “bvsym rot-” is the transform that
first performs clockwise 90o rotation and then vertical symmetry on
the lower half of the image.

Figure 1: Transformations of image (aji) into image (bji)

Output

For each test case:

Your program should output a single line whose contents is the minimal
number m (m > 0) such that is the identity. You may assume that, for
all test input, you have m < 231.

暴力模拟置换，分解成循环以后答案就是循环长度的最小公倍数。
复杂度是 $O(n^2m)$ ， $m$ 是操作个数。
注意分清 $mix$ 和 $mix-$ ，例如：

4
rot- mix
4
rot- mix-
0

答案是

6
3

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define R() for (int i=1;i<=n;i++) for (int j=1;j<=n;j++)
char s[1010];
int fx[2000][2000],fy[2000][2000],vis[2000][2000],n,n1;
int gcd(int a,int b)
{return b?gcd(b,a%b):a;
}
int lcm(int a,int b)
{return a/gcd(a,b)*b;
}
/*a[i][j]=f(a[i][j])*/
void init()
{int xx,yy;R() fx[i][j]=i,fy[i][j]=j;while (scanf("%s",s+1)&&(s[1]<'0'||s[1]>'9')){if (s[strlen(s+1)]!='-'){switch (s[1]){case 'r':R(){xx=fx[i][j];yy=fy[i][j];fx[i][j]=n-yy+1;fy[i][j]=xx;}break;case 's':R() fy[i][j]=n-fy[i][j]+1;break;case 'b':if (s[2]=='h')R() {
   if (fx[i][j]>n/2) fy[i][j]=n-fy[i][j]+1;}elseR() {
   if (fx[i][j]>n/2) fx[i][j]=n+n/2-fx[i][j]+1;}break;case 'd':R()if (fx[i][j]<=n/2) fx[i][j]=fx[i][j]*2-1;else fx[i][j]=(fx[i][j]-n/2)*2;break;case 'm':R()if (fx[i][j]&1){if (!(fy[i][j]&1)) fx[i][j]++;fy[i][j]=(fy[i][j]+1)/2;}else{if (fy[i][j]&1) fx[i][j]--;fy[i][j]=n/2+(fy[i][j]+1)/2;}break;}}else{switch (s[1]){case 'r':R(){xx=fx[i][j];yy=fy[i][j];fx[i][j]=yy;fy[i][j]=n-xx+1;}break;case 's':R() fy[i][j]=n-fy[i][j]+1;break;case 'b':if (s[2]=='h')R() {
   if (fx[i][j]>n/2) fy[i][j]=n-fy[i][j]+1;}elseR() {
   if (fx[i][j]>n/2) fx[i][j]=n+n/2-fx[i][j]+1;}break;case 'd':R()if (fx[i][j]&1) fx[i][j]=(fx[i][j]+1)/2;else fx[i][j]=fx[i][j]/2+n/2;break;case 'm':R()if (fy[i][j]<=n/2){fy[i][j]=fy[i][j]*2-(fx[i][j]&1);if (!(fx[i][j]&1)) fx[i][j]--;}else{fy[i][j]=(fy[i][j]-n/2)*2-(fx[i][j]&1);if (fx[i][j]&1) fx[i][j]++;}break;}}}sscanf(s+1,"%d",&n1);
}
int solve()
{int ret=1,now,xx,yy,tx,ty;R() vis[i][j]=0;R() if (!vis[i][j]){xx=fx[i][j];yy=fy[i][j];vis[xx][yy]=1;now=1;while (xx!=i||yy!=j){tx=xx;ty=yy;xx=fx[tx][ty];yy=fy[tx][ty];vis[xx][yy]=1;now++; }while (xx!=i||yy!=j);ret=lcm(ret,now);}return ret;
}
int main()
{scanf("%d",&n1);while (n=n1){init();printf("%d\n",solve());}
}