NOIP 普及 2011 第一轮 第 27 题：在矩阵中查找相同子矩阵：第 1 空

题目

完善程序
（子矩阵）给输入一个 $n_1\times m1$ 的矩阵 $a$，和 $n_2\times m_2$ 的矩阵 $b$，问 $a$ 中是否存在子矩阵和 $b$ 相等。若存在，输出所有子矩阵左上角的坐标：若不存在输出 $\texttt{There is no answer}$。

#include<iostream>
using namespace std;

const int SIZE = 50;

int n1,m1,n2,m2,a[SIZE][SIZE],b[SIZE][SIZE];

int main()
{
    int i,j,k1,k2;
    bool good ,haveAns;

    cin>>n1>>m1;
    for(i=1;i<=n1;i++)
       for(j=1;j<=m1;j++)
          cin>>a[i][j];

    cin>>n2>>m2;
    for(i=1;i<=n2;i++)
       for(j=1;j<=m2;j++)
           [   ①     ];

    haveAns=false;
    for(i=1;i<=n1-n2+1;i++)
       for(j=1;j<= [    ②     ];j++){
            [   ③    ];
           for(k1=1;k1<=n2;k1++)
               for(k2=1;k2<=[    ④    ] ;k2++){
                  if(a[i+k1-1][j+k2-1]!=b[k1][k2])
                     good=false;
               }
          if(good){
             cout<<i<<' '<<j<<endl;
             [       ⑤      ];
          }
       }
    if(!haveAns)
       cout<<"There is no answer"<<endl;

    return 0;
}

①处应填（ ）

答案

cin>>b[i][j]

题解

考点定位

本题（完善程序「矩阵查找」第①空）考「子矩阵读入」,对应大纲 4.2.1 模拟（难度【2】）。

程序思路：在大矩阵 a 中找与小矩阵 b 完全相同的子矩阵，输出左上角坐标。

解题过程

①处读入小矩阵：

``cpp cin >> b[i][j]; ``

与 a 的读入写法对称。答案：cin>>b[i][j]。

易错提醒

① 两重循环 i≤n2、j≤m2 别写反行列；② 读入格式与输出格式是完善程序的送分空。