枚举大矩阵中所有可放置位置，比较对应元素绝对差之和。
OJ: noi_openjudge
题目 ID: ch0112-04
难度:普及-
标签:枚举矩阵模拟python
日期: 2026-07-30 23:01
题意
在大矩阵中选择一个与给定小矩阵同尺寸的子矩阵，使对应元素差的绝对值和最小；并按左上角行、列优先打破平局。
思路
按行优先、列次优先枚举所有左上角位置，双层循环累加对应元素的绝对差。仅在严格更小时更新答案，因此相等时会自然保留先枚举到的行列更小的位置。最后按记录的位置切片输出。
代码
Python代码
python
row_count, column_count = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(row_count)]
pattern_rows, pattern_columns = map(int, input().split())
pattern = [list(map(int, input().split())) for _ in range(pattern_rows)]
best_position = (0, 0)
best_difference = float("inf")
for top in range(row_count - pattern_rows + 1):
for left in range(column_count - pattern_columns + 1):
difference = sum(
abs(matrix[top + row][left + column] - pattern[row][column])
for row in range(pattern_rows)
for column in range(pattern_columns)
)
if difference < best_difference:
best_difference = difference
best_position = (top, left)
top, left = best_position
for row in matrix[top : top + pattern_rows]:
print(*row[left : left + pattern_columns])C++代码
cpp
#include<iostream>
#include<cstdio>
using namespace std;
int A[105][105];
int B[105][105];
int m, n, r, s;
void init() {
scanf("%d%d",&m,&n);
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
scanf("%d",&A[i][j]);
scanf("%d%d",&r,&s);
for (int i = 1; i <= r; i++)
for (int j = 1; j <= s; j++)
scanf("%d",&B[i][j]);
}
int _abs(int a){
return a<0 ? -a:a;
}
int check(int x,int y){
int sum = 0;
for (int i = 1; i <= r; i++)
for (int j = 1; j <= s; j++)
sum += _abs(B[i][j] - A[x+i-1][y+j-1]);
return sum;
}
int main() {
init();
int x, y, max_ = 10000000,maxx,maxy;
for (y = 1; y <= m-r+1; y++)
for (x = 1; x <= n-s+1; x++) { //meiju
int t = check(y,x);
if ( t < max_) {
max_ = t;
maxx = y;
maxy = x;
}
}
for(int i =maxx;i <= maxx+r-1 ;i++){
for(int j = maxy;j <=maxy+s-1;j++){
printf("%d ",A[i][j]);
}
printf("\n");
}
return 0;
}复杂度
时间复杂度为
总结
枚举顺序与“平局选最小坐标”的规则一致时，更新条件只需使用严格小于。