题目描述
如果一个矩阵能够满足所有的行和列都是回文序列,则称这个矩阵为一个完美矩阵。
一个整数序列 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
算法1
(遍历) $O(n)$
“口”字形
“回”字形
时间复杂度
参考文献
python3 代码
T = int(input())
for _ in range(T):
[Row, Col] = [int(x) for x in input().split()]
grid = [[0 for _ in range(Col)] for _ in range(Row)]
for r in range(Row):
grid[r] = [int(x) for x in input().split()]
res = 0
for r in range(Row):
for c in range(Col):
a = [grid[r][c], grid[Row - 1 - r][c], grid[r][Col - 1 - c], grid[Row - 1 - r][Col - 1 - c]]
a.sort()
res += (a[3] + a[2] - a[0] - a[1])
res //= 4
print(res)
c++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T; cin >> T;
while(T --)
{
int Row; cin >> Row;
int Col; cin >> Col;
int grid[Row][Col];
memset(grid, 0, sizeof(grid));
for (int r = 0; r < Row; r ++)
for (int c = 0; c < Col; c++)
cin >> grid[r][c];
long long res = 0;
vector<int> a;
for (int r = 0; r < Row; r ++)
for (int c = 0; c < Col; c ++)
{
vector<int> a {grid[r][c], grid[Row - 1 - r][c], grid[r][Col - 1 - c], grid[Row - 1 - r][Col - 1 - c]};
sort(a.begin(), a.end());
res += (a[2] + a[3] - a[0] - a[1]);
}
res /= 4;
cout << res << endl;
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
orz