UVA 1156 - Pixel Shuffle(模拟+置换)

UVA 1156 - Pixel Shuffle

题目链接

题意：依据题目中的变换方式，给定一串变换方式，问须要运行几次才干回复原图像

思路：这题恶心的一比，先模拟求出一次变换后的相应的矩阵，然后对该矩阵求出全部循环长度，全部循环长度的公倍数就是答案

代码：

#include <stdio.h>
#include <string.h>

const int N = 1100;
int t, n, g[N][N], vis[N][N], save[N][N];
char str[N], s[N];

void rot(int flag) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!flag)
				save[i][j] = g[n - j - 1][i];
  			else
  				save[n - j - 1][i] = g[i][j];
    	}
	 }
 	for (int i = 0; i < n; i++)
 		for (int j = 0; j < n; j++)
 			g[i][j] = save[i][j];
}

void sym(int flag) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			save[i][j] = g[i][n - j - 1];
  		}
 	}
 	for (int i = 0; i < n; i++)
 		for (int j = 0; j < n; j++)
 			g[i][j] = save[i][j];
}

void bhsym(int flag) {
	for (int i = 0; i < n / 2; i++) {
		for (int j = 0; j < n; j++)
			save[i][j] = g[i][j];
 	}
 	for (int i = n / 2; i < n; i++)
 		for (int j = 0; j < n; j++)
 			save[i][j] = g[i][n - j - 1];
 	for (int i = 0; i < n; i++)
 		for (int j = 0; j < n; j++)
 			g[i][j] = save[i][j];
}

void bvsym(int flag) {
	for (int i = 0; i < n; i++) {
 		for (int j = 0; j < n; j++) {
 			if (i < n / 2)  save[i][j] = g[i][j];
			else save[i][j] = g[3 * n / 2 - 1 - i][j];
		}
 	}
 	for (int i = 0; i < n; i++)
 		for (int j = 0; j < n; j++)
 			g[i][j] = save[i][j];
}

void div(int flag) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!flag) {
				if (i % 2) save[i][j] = g[i / 2 + n / 2][j];
				else save[i][j] = g[i / 2][j];
			}
			else {
				if (i % 2) save[i / 2 + n / 2][j] = g[i][j];
				else save[i / 2][j] = g[i][j];
   			}
  		}
 	}
 	for (int i = 0; i < n; i++)
 		for (int j = 0; j < n; j++)
 			g[i][j] = save[i][j];
}

void mix(int flag) {
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (i % 2 == 0){
				if (flag) {
					if (j % 2 == 0) save[i][j] = g[i][j / 2];
					else save[i][j] = g[i + 1][j / 2];
				}
				else {
					if (j % 2 == 0) save[i][j / 2] = g[i][j];
					else save[i + 1][j / 2] = g[i][j];
    			}
			}else{
				if (flag) {
					if(j % 2 == 0) save[i][j] = g[i - 1][n / 2 + j / 2];
					else save[i][j] = g[i][n / 2 + j / 2];
				}
				else {
					if(j % 2 == 0) save[i - 1][n / 2 + j / 2] = g[i][j];
					else save[i][n / 2 + j / 2] = g[i][j];
    			}
			}
		}
	}
	for (int i = 0; i < n; i++)
 		for (int j = 0; j < n; j++)
 			g[i][j] = save[i][j];
}

void change(char *str) {
	int len = strlen(str);
	int flag = 1;
 	if (str[0] == '-') {
	 	flag = 0;
	 	str++;
 	}
	if (strcmp(str, "tor") == 0) rot(flag);
	else if (strcmp(str, "mys") == 0) sym(flag);
	else if (strcmp(str, "myshb") == 0) bhsym(flag);
	else if (strcmp(str, "mysvb") == 0) bvsym(flag);
	else if (strcmp(str, "vid") == 0) div(flag);
	else if (strcmp(str, "xim") == 0) mix(flag);
}

void tra() {
	int len = strlen(str);
 	int sn = 0;
 	for (int i = len - 1; i >= 0; i--) {
		if (str[i] == ' ') {
  			s[sn] = '\0';
			change(s);
			sn = 0;
  		}
  		else {
  			s[sn++] = str[i];
    	}
 	}
 	s[sn] = '\0';
 	change(s);
}

int gcd(int a, int b) {
	if (!b) return a;
	return gcd(b, a % b);
}

int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}

int solve() {
	int ans = 1;
	memset(vis, 0, sizeof(vis));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!vis[i][j]) {
				vis[i][j] = 1;
				int cnt = 1;
    			int x = g[i][j] / n;
				int y = g[i][j] % n;
				while (!vis[x][y]) {
					cnt++;
					vis[x][y] = 1;
					int t = g[x][y] / n;
					y = g[x][y] % n;
					x = t;
    			}
    			ans = lcm(ans, cnt);
   			}
  		}
 	}
 	return ans;
}

void init() {
	scanf("%d", &n);
	getchar();
	gets(str);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			g[i][j] = i * n + j;
  		}	
 	}
}

int main() {
	scanf("%d", &t);
	while (t--) {
		init();
		tra();
		printf("%d\n", solve());
		if (t) printf("\n");
 	}
	return 0;
}