title: CF1703E Mirror Grid 题解
date: 2022-07-15 11:54:20
categories: 
 - 题解

题目大意

给出一个由 \(0,1\) 组成的矩阵，求最少改变矩阵中的多少个数，使得矩阵旋转 \(0^\circ , 90^\circ , 180^\circ , 270^\circ\) 后相同。

思路

在一个 \(n \times n\) 的矩阵中，对于任意一点 \(P(i,j)\) 旋转 \(90^\circ , 180^\circ , 270^\circ\) 后的对应点分别位于 \(P_1(j,n-i+1),P_2(n-i+1,n-j+1),P_3(n-j+1,i)\)。所以只要让矩阵内所有的对应点相等， 矩阵在旋转后就会相同。

但是，当 \(n\) 为奇数时，循环就会出现少加或多加的情况，所以需要特判。

综上，对于每个 \(P\)，求出最少需要改变多少个数，使 \(P\) 和他所有的对应点相等， 当 \(n\) 是奇数时特判，求和即为答案。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
int n,t,a[110][110],ans;
int main()
{
	cin>>t;
	while(t--)
	{
		ans=0;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				char ch;
				cin>>ch;
				a[i][j]=ch-'0';
			}
		}
		for(int i=1;i<=n/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);//求和
			}
		}
		if(n%2==1)//特判
		{
			for(int i=1;i<=(n+1)/2;i++)
			{
				int j=(n+1)/2;
				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<<ans<<endl;
	}
}