对于 n 和 m 都是偶数的情况, 任意 t1 都存在其他三个兄弟.
但是当 n 、 m 有奇数的时候 有些格子只有一个兄弟.
我们可以取个巧 当 n 是偶数时 1 ~ n / 2 可以遍历左半部分. n 是奇数 1 ~ n / 2 也是遍历左半部分
但是 1 ~ (n + 1) / 2 当行列为奇数时,可以遍历到中间的行和列, 当行列为偶数时,由于下取整 偶数遍历区间没改变 也就是 n = 3 时 1 ~ 2 (4 / 2) n = 4 时 1 ~ 2 (5 / 2)
当i == n / 2 + 1时表示遍历到了中间的行或者列 n 是偶数时不会等 只有 n 是奇数是才能相等.
当n 、m 都是奇数时 最中间的格子不用管
时间复杂度 O(nm)
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 110;
LL q[N][N];
int main(void) {
int T;
cin >> T;
while (T --) {
int n, m;
cin >> n >> m;
LL ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> q[i][j];
for (int i = 1; i <= (n + 1) / 2; i++) {
for (int j = 1; j <= (m + 1) / 2; j++) {
int t1 = q[i][j], t2 = q[n - i + 1][j];
int t3 = q[i][m - j + 1], t4 = q[n - i + 1][m - j + 1];
if (i == n / 2 + 1 && j == m / 2 + 1) {
continue; //n、m都是奇数时 最中间的格子
} else if(i == n / 2 + 1)
ans += (LL)abs(t3 - t1); //n是奇数时 中间的行
else if (j == m / 2 + 1) {
ans += (LL)abs(t1 - t2); // m是奇数时 中间的列
} else {
vector<int> s; //有四个兄弟 取中位数
s.push_back(t1); s.push_back(t2); s.push_back(t3); s.push_back(t4);
sort(s.begin(), s.end());
ans += (LL)s[3] - s[0] + s[2] - s[1];
}
}
}
cout << ans << endl;
}
return 0;
}