题目描述

如果一个矩阵能够满足所有的行和列都是回文序列，则称这个矩阵为一个完美矩阵。

一个整数序列 a1,a2,…,ak
，如果满足对于任何整数 i（1≤i≤k），等式 ai=ak−i+1

均成立，则这个序列是一个回文序列。

给定一个 n×m
的矩阵 a，每次操作可以将矩阵中的某个元素加一或减一，请问最少经过多少次操作后，可以将矩阵 a

变为一个完美矩阵？
输入格式

第一行包含整数 T
，表示共有 T

组测试数据。

每组数据第一行包含整数 n
和 m

，表示矩阵的大小。

接下来 n
行，每行包含 m 个整数 aij

，表示矩阵中的元素。
输出格式

每组数据输出一行，一个答案，表示最少操作次数。
数据范围

1≤T≤10
,
1≤n,m≤100,
0≤aij≤109

输入样例：

2
4 2
4 2
2 4
4 2
2 4
3 4
1 2 3 4
5 6 7 8
9 10 11 18

输出样例：

8
42

样例解释

第一组数据可以通过 8

步操作得到以下矩阵：

2 2
4 4
4 4
2 2

第二组数据可以通过 42

步操作得到以下矩阵：

5 6 6 5
6 6 6 6
5 6 6 5

C++ 代码

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int,int>  PII;
const int N=110;
int n,m;
int w[N][N];
LL calc(set<PII>S)
{
    vector<int> q;
    for(auto& p :S)   q.push_back(w[p.x][p.y]);
    sort(q.begin(),q.end());
    LL ret=0;
    for(int i=0;i< q.size();i++)
     ret+=abs(q[i]-q[q.size()/2]);
     return ret;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
          for(int j=0;j<m;j++)
            scanf("%d",&w[i][j]);

            LL res=0;

            for(int i=0;i<=n-1-i;i++)
                for(int j=0;j<=m-1-j;j++)
                res+=calc({{i,j},{i,m-1-j},{n-1-i,j},{n-1-i,m-1-j}});

    printf("%lld\n",res);
    }

    return 0;
}