首页 > > 程序设计 > C/C++ >

04:最匹配的矩阵

2018-06-17 23:10:21来源：未知阅读 ()

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个整数，整数之间以一个空格分开。

样例输入

样例输出

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 }