自动搬运

查看原文

来自洛谷，原作者为

	ix35 垒球

搬运于2025-08-24 22:25:49，当前版本为作者最后更新于2021-06-15 13:14:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

显然一个格子上的数只能到达横向和竖向翻转后对称的 $4$ 个格子。

考虑这样一个“等价类”中的 $4$ 个数 $a,b,c,d$，如何能在不影响其他格子的数的情况下进行它们之间的置换。

简单考虑发现，我们可以以顺时针或逆时针方向旋转其中任意三个格子，具体做法是形如 $\texttt{URU'R'}$，这有点类似三阶魔方中的顶面三棱换。

于是我们可以算出这些可能的置换作用于 $\begin{bmatrix} a\quad b\\ c\quad d\end{bmatrix}$ 上的置换群，例如 $\begin{bmatrix} b\quad a\\ c\quad d\end{bmatrix}$ 这样是无法生成的，而 $\begin{bmatrix} b\quad a\\ d\quad c\end{bmatrix}$ 是可以生成的。

事实上我们只需先将 $a$ 换到左上角，然后看看剩下的三个是不是逆时针排列为 $b,c,d$ 的即可。

那么本题的做法如下：

• 先将四个角还原，此时可以随便操作，只要四个角对上就可以了；

• 再将四条边还原，但此时不能动角块，例如还原上下边时保证进行行翻转偶数次，而左右边时保证进行列翻转偶数次；

• 再将中间还原，只能按照上面所说的几种置换复合来实现。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=110;
int t,n,m,cnt,a[MAXN][MAXN],md[MAXN*MAXN*10][2];
int hs (int x,int y) {return (x-1)*m+y;}
void trip (int x,int y,int t) {
	if (t==1) {
		cnt++;
		md[cnt][0]=2,md[cnt][1]=y;
		cnt++;
		md[cnt][0]=1,md[cnt][1]=x;
		cnt++;
		md[cnt][0]=2,md[cnt][1]=y;
		cnt++;
		md[cnt][0]=1,md[cnt][1]=x;
		swap(a[x][y],a[x][m-y+1]);
		swap(a[x][y],a[n-x+1][y]);
	} else if (t==2) {
		cnt++;
		md[cnt][0]=1,md[cnt][1]=x;
		cnt++;
		md[cnt][0]=2,md[cnt][1]=m-y+1;
		cnt++;
		md[cnt][0]=1,md[cnt][1]=x;
		cnt++;
		md[cnt][0]=2,md[cnt][1]=m-y+1;
		swap(a[x][y],a[n-x+1][m-y+1]);
		swap(a[x][m-y+1],a[n-x+1][m-y+1]);
	} else if (t==3) {
		cnt++;
		md[cnt][0]=1,md[cnt][1]=n-x+1;
		cnt++;
		md[cnt][0]=2,md[cnt][1]=y;
		cnt++;
		md[cnt][0]=1,md[cnt][1]=n-x+1;
		cnt++;
		md[cnt][0]=2,md[cnt][1]=y;
		swap(a[x][y],a[n-x+1][y]);
		swap(a[n-x+1][y],a[n-x+1][m-y+1]);
	} else {
		cnt++;
		md[cnt][0]=2,md[cnt][1]=m-y+1;
		cnt++;
		md[cnt][0]=1,md[cnt][1]=n-x+1;
		cnt++;
		md[cnt][0]=2,md[cnt][1]=m-y+1;
		cnt++;
		md[cnt][0]=1,md[cnt][1]=n-x+1;
		swap(a[x][m-y+1],a[n-x+1][m-y+1]);
		swap(a[x][m-y+1],a[n-x+1][y]);
	}
	return;
}
int solve (int x,int y,int t) {
	int uu=a[x][y],vv=a[x][m-y+1],xx=a[n-x+1][y],yy=a[n-x+1][m-y+1];
	int tmp1[5],tmp2[5];
	tmp1[1]=uu,tmp1[2]=vv,tmp1[3]=xx,tmp1[4]=yy;
	tmp2[1]=hs(x,y),tmp2[2]=hs(x,m-y+1),tmp2[3]=hs(n-x+1,y),tmp2[4]=hs(n-x+1,m-y+1);
	sort(tmp1+1,tmp1+5);
	sort(tmp2+1,tmp2+5);
	for (int i=1;i<=4;i++) {if (tmp1[i]!=tmp2[i]) {return 0;}}
	int u=(uu>vv)+(uu>xx)+(uu>yy)+1,v=(vv>uu)+(vv>xx)+(vv>yy)+1;
	int xxx=(xx>uu)+(xx>vv)+(xx>yy)+1,yyy=(yy>uu)+(yy>vv)+(yy>xx)+1;
	if (v==1) {
		trip(x,y,2),trip(x,y,2);
	} else if (xxx==1) {
		trip(x,y,1);
	} else if (yyy==1) {
		trip(x,y,2);
	}
	uu=a[x][y],vv=a[x][m-y+1],xx=a[n-x+1][y],yy=a[n-x+1][m-y+1];
	u=(uu>vv)+(uu>xx)+(uu>yy)+1,v=(vv>uu)+(vv>xx)+(vv>yy)+1;
	xxx=(xx>uu)+(xx>vv)+(xx>yy)+1,yyy=(yy>uu)+(yy>vv)+(yy>xx)+1;
	if (xxx==2) {
		trip(x,y,4);
	} else if (yyy==2) {
		trip(x,y,4),trip(x,y,4);
	}
	uu=a[x][y],vv=a[x][m-y+1],xx=a[n-x+1][y],yy=a[n-x+1][m-y+1];
	u=(uu>vv)+(uu>xx)+(uu>yy)+1,v=(vv>uu)+(vv>xx)+(vv>yy)+1;
	xxx=(xx>uu)+(xx>vv)+(xx>yy)+1,yyy=(yy>uu)+(yy>vv)+(yy>xx)+1;
	if (xxx==3) {return 1;}
	if (t==0) {return 0;}
	if (t==1) {
		cnt++;
		md[cnt][0]=1,md[cnt][1]=n-x+1;
		for (int i=1;i<=m/2;i++) {swap(a[n-x+1][i],a[n-x+1][m-i+1]);}
	} else {
		cnt++;
		md[cnt][0]=2,md[cnt][1]=y;
		for (int i=1;i<=n/2;i++) {swap(a[i][y],a[n-i+1][y]);}
		trip(x,y,3);
	}
	return 1;
}
void print () {
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			printf("%d ",a[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	return;
}
int main () {
	scanf("%d",&t);
	for (int ii=1;ii<=t;ii++) {
		scanf("%d%d",&n,&m); 
		swap(n,m);
		cnt=0;
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=m;j++) {
				scanf("%d",&a[i][j]);
			}
		}
		int flg=0;
		if (n!=1&&m!=1) {
			
		for (int i=1;i<=n/2;i++) {
			if (!solve(i,1,1)) {flg=1;break;}
		}
		for (int j=2;j<=m/2;j++) {
			if (!solve(1,j,2)) {flg=1;break;}
		}
		
		}
		//print();
		for (int i=2;i<=n/2;i++) {
			if (flg) {break;}
			for (int j=2;j<=m/2;j++) {
				if (!solve(i,j,0)) {
					flg=1;
					break;
				}
			}
		}
		//print();
		if (n%2==1) {
			int flg2=1,rw=(n+1)/2;
			for (int i=1;i<=m;i++) {
				if (a[rw][i]!=hs(rw,i)) {flg2=0;break;}
			}
			if (!flg2) {
				flg2=1;
				for (int i=1;i<=m;i++) {
					if (a[rw][i]!=hs(rw,m-i+1)) {flg2=0,flg=1;break;}
				}
				if (flg2) {
					cnt++;
					md[cnt][0]=1,md[cnt][1]=rw;
					for (int i=1;i<=m/2;i++) {swap(a[rw][i],a[rw][m-i+1]);}
				}
			}
		}
		if (m%2==1) {
			int flg2=1,col=(m+1)/2;
			for (int i=1;i<=n;i++) {
				if (a[i][col]!=hs(i,col)) {flg2=0;break;}
			}
			if (!flg2) {
				flg2=1;
				for (int i=1;i<=n;i++) {
					if (a[i][col]!=hs(n-i+1,col)) {flg2=0,flg=1;break;}
				}
				if (flg2) {
					cnt++;
					md[cnt][0]=2,md[cnt][1]=col;
					for (int i=1;i<=n/2;i++) {swap(a[i][col],a[n-i+1][col]);}
				}
			}
		}
		if (flg) {
			printf("IMPOSSIBLE\n");
		} else {
			printf("POSSIBLE %d",cnt);
			for (int i=1;i<=cnt;i++) {
				if (md[i][0]==1) {printf(" R%d",md[i][1]);}
				else {printf(" C%d",md[i][1]);}
			}
			printf("\n");
		}
	}
	return 0;
}