题解Ⅱ级（）

时间限制: 1000 ms  空间限制: 262144 KB

题目描述 

  给定一个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矩阵中的各行，数与数之间以一个空格分开。

输出

  输出矩阵C，一共r行，每行s个整数，整数之间以一个空格分开。

样例输入

3 3
3 4 5
5 3 4
8 2 4
2 2
7 3
4 9
样例输出

4 5

3 4

数据范围限制

  1<=m<=100,1<=n<=100

问题分析

  求最小值问题，穷举法就可以解决。没有想出其他好办法。

程序说明

  需要处理好下标之间的映射关系。

  程序的处理基本上都是套路。

要点详解

存储恰到好处就可以了。

#include <stdio.h>  

#include <stdlib.h>  

  

#define MAX_INT ~((unsigned int)0) >> 1;  

#define N 100  

  

int a[N][N], b[N][N];  

  

int main(void)  

{  

    int m, n, r, s, i, j;  

  

    scanf("%d%d", &m, &n);  

    for(i=0; i<m; i++)  

        for(j=0; j<n; j++)  

            scanf("%d", &a[i][j]);  

  

    scanf("%d%d", &r, &s);  

    for(i=0; i<r; i++)  

        for(j=0; j<s; j++)  

            scanf("%d", &b[i][j]);  

  

    int drow, dcol, min;  

    min = MAX_INT;  

    for(i=0; i<m-r+1; i++)  

        for(j=0; j<n-s+1; j++) {  

            int k, l, sum;  

            sum = 0;  

            for(k=0; k<r; k++)  

                for(l=0; l<s; l++)  

                    sum += abs(a[i + k][j +l] - b[k][l]);  

            if(sum < min) {  

                drow = i, dcol = j;  

                min = sum;  

            }  

        }  

  

    for(i=0; i<r; i++) {  

        for(j=0; j<s; j++)  

            printf("%d ", a[drow + i][dcol + j]);  

        printf("\n");  

    }  

  

    return 0;  

}