CF1703E Mirror Grid

题意

给定一个 \(n\times n\ (n\le100)\) 的 01 矩形，求至少修改多少次后能使矩形旋转 0°，90°，180°，270°后所形成的矩形都完全相同。

思路

吸纳分为两种情况讨论：

\(n\)为奇数

那么会出现这种情况：（以\(5\times 5\)为例）

如上图，我们就可以将其分为五个部分，每个部分都能通过旋转得到其他三个（中间的白色除外）

所以，我们只需要查看上图中黄色的部分，并且算出来它旋转若干次后的位置的坐标即可

\(n\)为偶数（以\(4\times 4\)为例）

所以划分就是上图，亦能够将其分成四个相同的部分并通过旋转得到彼此

所以，当我们枚举两张图中的黄色部分时，黄色部分中的格子做对应的旋转若干度后的格子都是已知的，那么就可以将他们加和，看看是和\(4\)接近还是和\(0\)接近（即全部变为\(1\)还是全部变为\(0\)）

代码

#include<bits/stdc++.h>
using namespace std;
const int Maxn=110;
int a[Maxn][Maxn];
int n,ans;
void run()
{
	cin>>n;ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			char c;
			cin>>c;
			a[i][j]=c-'0';
		}
	for(int i=1;i<=(n+1)/2;i++)
		for(int j=1;j<=n/2;j++)
		{
			int cnt=a[i][j]+a[n-j+1][i]+a[j][n-i+1]+a[n-i+1][n-j+1];
			ans+=min(cnt,4-cnt);
//			cout<<i<<" "<<j<<" "<<ans<<endl;
		}
	cout<<ans<<endl; 
}
int main()
{
	int t;
	cin>>t;
	while(t--) run();
 }