根据本题的性质,一个点的值应该联系着另外三个点或一个点或零个点,即这几个点的应该相等。
所以只要遍历矩阵的左上角部分即可,然后问题就变成将这若干个点的值变相同的最小步数,记最终的值$x$,那么步数就是$\sum{|a[i]-x|}$,这用绝对值不等式定理即可解决。
#include <iostream>
#include <algorithm>
#define pb push_back
using namespace std;
typedef long long LL;
const int N = 110;
LL a[N][N] , n , m;
int main()
{
int T;
cin >> T;
while(T--)
{
LL res = 0;
cin >> n >> m;
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < m ; j++)
cin >> a[i][j];
//边界向上取整,不然会漏掉
for(int i = 0 ; i < (n + 1) / 2 ; i++)
for(int j = 0 ; j < (m + 1) / 2 ; j++)
{
vector<int> vec;
vec.pb(a[i][j]);
//如果是不同的点则是与a[i][j]有联系的点
if(i != n - i - 1) vec.pb(a[n - i - 1][j]);
if(j != m - j - 1) vec.pb(a[i][m - j - 1]);
if(i != n - i - 1 && j != m - j - 1) vec.pb(a[n - i - 1][m - j - 1]);
//根据绝对值不等式定理计算即可
sort(vec.begin() , vec.end());
if(vec.size() == 2)
res += vec[1] - vec[0];
else if(vec.size() == 4) res += vec[3] + vec[2] - vec[1] - vec[0];
}
cout << res << endl;
}
}