正经题解｜完美矩阵

题目大意

给出一个$n$,$n$必然是偶数。 同时给出一个$n \times n$的矩阵，你要保证这个矩阵翻转$90°$之后，每个位置上的字符不发生变化。你可以对矩阵当中任意一个字符进行字典序+1的操作。

题目目的

求达成完美矩阵的最少操作次数

算法与时间

不难可以推理出，在一个必然为正方形的矩阵上面，如果进行翻转360°，每个位置的字符能够到达的地方是一致的。

举个例子，假如矩阵为

aaaa
abba
abba
aaaa

枚举其中几个字符坐标旋转发生的变化为

$1,1 -> 1,4 -> 4,4 -> 4,1 -> 1,1$

$1,2 -> 2,4 -> 4,3 -> 3,1 -> 1,2$

然后我们便可以推理出，四个字符必须保持一致，才可以让矩阵旋转后保持不变。

同时题目要求只能+1的操作，那么意味着你只能将某一个字符往前+1，而不能往后-1，这就规避掉了我们在四个字符当中选取中间值进行操作的情况。那么根据最优选择，那便是选择四个字符当中字典序最大的作为标准，然后进行统一。

那么我们可以把这个矩阵分为四部分(因为n一定为偶数)，遍历其中第一部分的每一个字符，枚举旋转90°后其他三个字符的坐标即可。

难点是在怎么计算坐标，其实根据上面的例子，我们就可以发现了。

我们设置当前处于第i行，第j列(下标从1开始)，然后来列公式，通过观察(1,2)可得知

第一个坐标为$i,j$ 第二个坐标为$j,n-i+1$,第三个坐标$n-i+1,n-j+1$,第四个坐标$n-j+1,i$

我们会发现，每个坐标的行下标相当于前一个坐标的列下标，列下表相当于N减去前一个坐标的行下表+1.
推理出四个方向的坐标后，根据只能往前挪动一格的条件，我们就可以的得出每项的通项公式为

$max(第一个坐标的字符,第二个坐标的字符,第三个坐标的字符,第四个坐标的字符) - 剩余其他坐标的字符$ 即可得到四个位置字符一致的操作次数。

代码示范

#include<bits/stdc++.h>
using namespace std;
char mp[1005][1005];
void solve()
{
	int n;
	cin >> n ;
	for(int i = 1 ; i  <= n ; i ++ )
	{
		for(int j = 1 ; j <= n ; j ++ )
		{
			cin >> mp[i][j];
		}
	}
	long long sum = 0 ;
	for(int i = 1 ; i <= n/2 ; i ++ )
	{
		for(int j = 1 ; j <= n/2 ; j ++ )
		{
			int x2,x3,x4,y2,y3,y4;
			x2 = j ,y2 = n - i + 1 ;
			x3 = n - i + 1 , y3 = n - j + 1;
			x4 = n - j + 1 , y4 = i;
			char mx = max(mp[i][j],max(mp[x2][y2],max(mp[x3][y3],mp[x4][y4])));
			sum += 4 * mx - mp[i][j] - mp[x2][y2] - mp[x3][y3] - mp[x4][y4]; 
		}
	}
	cout << sum << endl;
}

int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}