描述: 以二维数组表示图像, 其值只有 01 两种, 寻找两幅图像中最大的相同部分
输入: 第一行输入一个 n, 接下来的 2n 行输入两个 n * n 数组, 寻找一个最大的 m * m 子区域, 使得两个数组在该子区域完全相同
输出: 输出上诉 m
样例输入:
- 4
- 1 1 1 1
- 1 1 1 0
- 1 1 1 0
- 1 1 1 1
- 0 1 1 1
- 0 1 1 1
- 0 1 1 1
- 0 1 1 0
样例输出:
- 2
- #include <iostream>
- #define N 100
- using namespace std;
- bool num(int b[N][N],int i,int j,int t){
- bool flag=true;
- for(int k=i;k<i+t;k++){
- for(int d=j;d<j+t;j++){
- if(b[k][d]==0){
- flag=false;
- break;
- }
- }
- }
- return flag;
- }
- int main()
- {
- int n;
- scanf("%d",&n);
- int a[N][N];
- for(int i=0;i<n;i++)
- for(int j=0;j<n;j++)
- scanf("%d",&a[i][j]);
- int temp;
- for(int i=0;i<n;i++){
- for(int j=0;j<n;j++){
- scanf("%d",&temp);
- a[i][j]=!(a[i][j]^temp);
- }
- }
- int t=n;
- bool tmp=true;
- while(tmp){
- for(int i=0;i<n-t;i++){
- for(int j=0;j<n-t;j++){
- if(num(a,i,j,t)){
- tmp=false;
- break;
- }
- }
- }
- t--;
- }
- printf("%d",t+1);
- return 0;
- }
P.S. 我做是做出来了, 但这个的时间复杂度 O(n^4), 也可以看到, 实在太大了, 我估计要是跑 oj 的话是要超时的
来源: http://www.bubuko.com/infodetail-2540727.html