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 } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 08:矩阵加法

    08:矩阵加法 总时间限制: 1000ms 内存限制: 65536kB描述 输入两个n行m列的矩阵A和B,输出它们的和A+B。 输入第一行包含两个整数n和...

    attack
  • 1026 逃跑的拉尔夫

    1026 逃跑的拉尔夫 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 年轻的...

    attack
  • codeforces736D. Permutations(线性代数)

    attack
  • CodePlus 第五次网络赛 我有矩阵,你有吗?(思维+枚举)

    题目链接:https://oj.thusaac.org/#!/contest/136/problem/2   (要报名才能看题交题)

    Ch_Zaqdt
  • 浙大版《C语言程序设计(第3版)》题目集 习题7-3 判断上三角矩阵

    上三角矩阵指主对角线以下的元素都为0的矩阵;主对角线为从矩阵的左上角至右下角的连线。

    C you again 的博客
  • 【2020HBU天梯赛训练】7-8 矩阵A乘以B

    给定两个矩阵A和B,要求你计算它们的乘积矩阵AB。需要注意的是,只有规模匹配的矩阵才可以相乘。即若A有R​a​​行、C​a​​列,B有R​b​​行、C​b​​列...

    韩旭051
  • 08:矩阵加法

    08:矩阵加法 总时间限制: 1000ms 内存限制: 65536kB描述 输入两个n行m列的矩阵A和B,输出它们的和A+B。 输入第一行包含两个整数n和...

    attack
  • 腾讯2016春招之算法编程解析

    第一道题:求有删除情况的最长回文子串 题目: ? 解题思路: 这个题严格意义上来说,删除了字符就谈不上回文串了,既然有删除,那估计考察的不是回文串,而是其他的...

    CloudDeveloper
  • P1028 数的计算

    思路:通过演算,我们很容易就能得到, f[1] = 1; f[2] = f[1] +1; f[3] = f[1] + 1; f[4] = f[2] + ...

    用户7727433
  • Codeforces Round #513 C. Maximum Subrectangle(思维)

    题目链接:http://codeforces.com/contest/1060/problem/C

    Ch_Zaqdt

扫码关注云+社区

领取腾讯云代金券