#112. 枚举算法(NOIP2011)子矩阵

枚举算法(NOIP2011)子矩阵

(NOIP2011)子矩阵

输入一个n1 * m1的矩阵a和一个n2 * m2的矩阵b,问a中是否存在子矩阵和b相等。若存在,输出所有子矩阵左上角的坐标;若不存在,输出"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;
}

①处应填( )。
{{ select(1) }}

  • cin>>b[i][j]
  • cin>>a[i][j]
  • cin>>b[n1][m1]
  • cin>>b[n2][m2]

②处应填( )。
{{ select(2) }}

  • m1
  • m1-m2+1
  • m1-1
  • m1+1

③处应填( )。
{{ select(3) }}

  • good=0
  • good='1'
  • good=false
  • good=1

④处应填( )。
{{ select(4) }}

  • k1+1
  • m2
  • m2-1
  • k1

⑤处应填( )。
{{ select(5) }}

  • break
  • return
  • haveAns=true
  • haveAns=false