CF1881C 题解

思路分析

这道题的难点主要是在将一个矩阵旋转 $90 \degree$ 以后的关系处理出来。

但是其实，我们可以按位置，一个一个进行枚举推测。

假设我们现在有一个矩阵：

$$
1 ⋅ ⋅ ⋅ ⋅ 2
$$

$$
\dots \dots
$$

$$
\dots \dots
$$

$$
4 ⋅ ⋅ ⋅ ⋅ 3
$$

那么我们就将 $4$ 移到 $1$，$1$ 移到 $2$，$2$ 移到 $3$，$3$ 移到 $4$。

然后依次往后顺延

$$
⋅ 1⋅ ⋅ ⋅ ⋅
$$

$$
⋅ ⋅ ⋅ ⋅ ⋅ 2
$$

$$
4 ⋅ ⋅ ⋅ ⋅ ⋅
$$

$$
⋅ ⋅ ⋅ ⋅ 3⋅
$$

接着将 $4$ 移到 $1$，$1$ 移到 $2$，$2$ 移到 $3$，$3$ 移到 $4$。

$$
\dots \dots
$$

如此往复，最终求出最后的矩阵。

所以可以通过转的方法，发现其实 $a_{i,j}$ 和 $a_{j,n-i+1}$ 是旋转后对应的，同理就可以得出最终 $a_{i,j},a_{j,n-i+1},a_{n-j+1,i},a_{n-i+1,n-j+1}$ 都是对应的。

所以就可以得出代码。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
char a[1000+10][1000+10];
bool vis[1000+10][1000+10];
long long ans;
int main(){
	ios_base::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--){
		cin>>n;
		ans=0;
		memset(vis,0,sizeof vis);
		for(int i=1;i<=n;++i) cin>>a[i]+1;
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				if(vis[i][j]) continue;
				vis[i][j]=vis[n-j+1][i]=vis[j][n-i+1]=vis[n-i+1][n-j+1]=1;
				int want=max({a[i][j],a[j][n-i+1],a[n-j+1][i],a[n-i+1][n-j+1]});
				for(char k:{a[i][j],a[j][n-i+1],a[n-j+1][i],a[n-i+1][n-j+1]}) ans+=want-k;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}