#10765. 枚举算法(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