04:最匹配的矩阵
04:最匹配的矩阵
总时间限制: 1000ms 内存限制: 65536kB描述
给定一个m*n的矩阵A和r*s的矩阵B,其中0 < r ≤ m, 0 < s ≤ n，A、B所有元素值都是小于100的正整数。求A中一个大小为r*s的子矩阵C，使得B和C的对应元素差值的绝对值之和最小，这时称C为最匹配的矩阵。如果有多个子矩阵同时满足条件，选择子矩阵左上角元素行号小者，行号相同时，选择列号小者。
输入第一行是m和n，以一个空格分开。 之后m行每行有n个整数，表示A矩阵中的各行，数与数之间以一个空格分开。 第m+2行为r和s，以一个空格分开。 之后r行每行有s个整数，表示B矩阵中的各行，数与数之间以一个空格分开。 （1 ≤ m ≤ 100,1 ≤ n ≤ 100）输出输出矩阵C，一共r行，每行s个整数，整数之间以一个空格分开。样例输入
3 3
3 4 5
5 3 4
8 2 4
2 2
7 3
4 9样例输出
4 5
3 4 来源医学部 2010 期末试题 林洪武
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<cmath>
5 #include<queue>
6 #include<vector>
7 #include<algorithm>
8 using namespace std;
9 int n,m;//大矩阵的长宽
10 int r,s;//小矩阵的长宽
11 int a[1001][1001];//大
12 int b[1001][1001];//小
13 int minn=1000000;//储存最小的绝对值
14 int minnow;
15 int wzh;//储存最匹配矩阵的位置
16 int wzl;
17 void find()
18 {
19 for(int i=1;i<=n-r+1;i++)
20 {
21 for(int j=1;j<=m-s+1;j++)
22 {
23 minnow=0;
24 for(int k=i;k<=i+r-1;k++)
25 {
26 for(int l=j;l<=s+j-1;l++)
27 {
28 minnow=minnow+abs(a[k][l]-b[k-i+1][l-j+1]);
29 }
30 }
31 if(minnow<minn)
32 {
33 wzh=i;
34 wzl=j;
35 minn=minnow;
36
37 }
38 }
39 }
40 }
41 int main()
42 {
43 cin>>n>>m;
44 for(int i=1;i<=n;i++)
45 {
46 for(int j=1;j<=m;j++)
47 {
48 cin>>a[i][j];
49 }
50 }
51 cin>>r>>s;
52 for(int i=1;i<=r;i++)
53 {
54 for(int j=1;j<=s;j++)
55 {
56 cin>>b[i][j];
57 }
58 }
59 find();
60 for(int i=wzh;i<=wzh+r-1;i++)
61 {
62 for(int j=wzl;j<=wzl+s-1;j++)
63 {
64 cout<<a[i][j]<<" ";
65 }
66 cout<<endl;
67 }
68 return 0;
69 } 本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-03-09 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录