04:最匹配的矩阵

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

新老客户大回馈,云服务器低至5折

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 } 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:26:字符串最大跨距

下一篇:C++primer拾遗(第一章:开始)