[小模拟]zoj 3838

题意

      问需要修改多少个点使得这个正方形完全对称。

思路

     针对在对角线上的点，在中间线上的点还有剩下的点分别求出需要修改的最少点数，相加即可。

    点(x,y)关于主对角线对称的点是(y,x)，关于副对角线对称的点是(n-1-y,n-1-x)。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 100;
char str[nMax][nMax];
int n;
char vis[400];
int max(int a,char b){
    int c = b;
    if(a>c)return a;
    return c;
}
int main(){
    int tcs ,i ,j ,ans ,m;
    scanf("%d",&tcs);
    while(tcs--){
        scanf("%d",&n);
        for(i=0;i<n;i++){
            scanf("%s",str[i]);
        }
        m = n/2;
        ans = 0;
        for(i = 0 ;i< m ;i++){
            for(j = 0;j < m;j ++){
                if(i < j){
                    memset(vis,0,sizeof(vis));
                    vis[str[i][j]]++;
                    vis[str[j][i]]++;
                    vis[str[n-j-1][i]]++;
                    vis[str[n-i-1][j]]++;
                    vis[str[n-i-1][n-j-1]]++;
                    vis[str[n-j-1][n-i-1]]++;
                    vis[str[j][n-i-1]]++;
                    vis[str[i][n-j-1]]++;
                    int tmp = 0;
                    tmp = max(vis[str[i][j]],vis[str[j][i]]);
                    tmp = max(tmp,vis[str[j][i]]);
                    tmp = max(tmp,vis[str[n-j-1][i]]);
                    tmp = max(tmp,vis[str[n-i-1][j]]);
                    tmp = max(tmp,vis[str[n-i-1][n-j-1]]);
                    tmp = max(tmp,vis[str[n-j-1][n-i-1]]);
                    tmp = max(tmp,vis[str[j][n-i-1]]);
                    tmp = max(tmp,vis[str[i][n-j-1]]);
                    ans += 8-tmp;
                }
            }
        }
        for(i = 0;i<m;i++){
            memset(vis,0,sizeof(vis));
            vis[str[i][i]]++;
            vis[str[i][n-i-1]]++;
            vis[str[n-i-1][i]]++;
            vis[str[n-i-1][n-i-1]]++;
            int tmp = 0;
            tmp=max(vis[str[i][i]],vis[str[i][n-i-1]]);
            tmp=max(tmp,vis[str[n-i-1][i]]);
            tmp=max(tmp,vis[str[n-i-1][n-i-1]]);
            ans += 4-tmp;
        }
        for(i=0;i<m;i++){
            memset(vis,0,sizeof(vis));
            vis[str[i][m]]++;
            vis[str[m][i]]++;
            vis[str[n-i-1][n-m-1]]++;
            vis[str[n-m-1][n-i-1]]++;
            int tmp = 0;
            tmp = max(vis[str[i][m]],vis[str[m][i]]);
            tmp = max(tmp, vis[str[n-i-1][n-m-1]]);
            tmp = max(tmp,vis[str[n-m-1][n-i-1]]);
            ans += 4-tmp;
        }
        printf("%d\n",ans);
    }
    return 0;
}