【ybtoj高效进阶 21281】矩阵逆转(模拟)

矩阵逆转

题目链接:ybtoj高效进阶 21281

题目大意

给你一个矩阵,每行每列都是一个排列,要你维护一些操作:
把所有列右移或者左移,把所有行上移或者下移,或者将每一行或每一列对于的排列对于的置换求逆。
输出最后的矩阵即可。

思路

考虑这些数会左右移动,还会有置换。
相当于把这些数有三者属性:\(i,j\) 表示当前的行列,\(x\) 表示这个数的值。

然后你再想想求逆的是什么鬼。
你会发现每一行求逆就是交换 \(j,x\),每一列求逆就是交换 \(i,x\)。

你预处理行列的位移,然后用三个变量分别记录一开始的 \(i,j,x\) 现在分别对应的位置。
然后就简单修改一下。

接着你就把数组根据你记录的位移和对应的位置复原出来即可。

代码

#include<cstdio>
#include<algorithm>

using namespace std;

int n, m, a[1001][1001][4];
int cnt[4], h, l, id[4];
int ans[1001][1001];
char c[100001];

int main() {
//	freopen("mat.in", "r", stdin);
//	freopen("mat.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			a[i][j][1] = i; a[i][j][2] = j;
			scanf("%d", &a[i][j][3]);
		}
	scanf("%s", c + 1);
	
	id[1] = 1; id[2] = 2; id[3] = 3;
	for (int i = 1; i <= m; i++) {
		if (c[i] == 'R') cnt[2]++;
		if (c[i] == 'L') cnt[2]--;
		if (c[i] == 'D') cnt[1]++;
		if (c[i] == 'U') cnt[1]--;
		if (c[i] == 'I') {
			swap(cnt[2], cnt[3]);
			swap(id[2], id[3]);
		}
		if (c[i] == 'C') {
			swap(cnt[1], cnt[3]);
			swap(id[1], id[3]);
		}
	}
	
	for (int i = 1; i <= n; i++)//复原回去
		for (int j = 1; j <= n; j++) {
			ans[((a[i][j][id[1]] + cnt[1] - 1) % n + n) % n + 1][((a[i][j][id[2]] + cnt[2] - 1) % n + n) % n + 1] = ((a[i][j][id[3]] + cnt[3] - 1) % n + n) % n + 1;
		}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			printf("%d ", ans[i][j]);
		putchar('\n'); 
	}
	
	return 0;
}
上一篇:《ybtoj高效进阶》第二部分第二章例题5 子正方形


下一篇:Redis数据类型