BZOJ 1567: [JSOI2008]Blue Mary的战役地图

1567: [JSOI2008]Blue Mary的战役地图

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1011 Solved: 578
[Submit][Status][Discuss]

Description

Blue Mary最近迷上了玩Starcraft(星际争霸) 的RPG游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。由于Blue Mary的技术已经达到了一定的高度,因此，对于用同一种打法能够通过的战役地图，她只需要玩一张，她就能了解这一类战役的打法，然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法，因此Blue Mary需要你写一个程序，来帮助她判断哪些地图是属于同一类的。具体来说，Blue Mary已经将战役地图编码为n*n的矩阵，矩阵的每个格子里面是一个32位（有符号）正整数。对于两个矩阵，他们的相似程度定义为他们的最大公共正方形矩阵的边长。两个矩阵的相似程度越大，这两张战役地图就越有可能是属于同一类的。

Input

第一行包含一个正整数n。以下n行，每行包含n个正整数，表示第一张战役地图的代表矩阵。再以下n行，每行包含n个正整数，表示第二张战役地图的代表矩阵。

Output

仅包含一行。这一行仅有一个正整数，表示这两个矩阵的相似程度。

Sample Input

3
1 2 3
4 5 6
7 8 9
5 6 7
8 9 1
2 3 4

Sample Output

HINT

样例解释：

子矩阵：
5 6
8 9
为两个地图的最大公共矩阵

约定：
n<=50

题目大意：求两个矩形的最大公共子正方形的边长

题解：O(n^7)暴力...从大到小枚举边长

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n;

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

inline int read(){

    char ch=getchar();int x=,f=;

    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';

    return x*f;

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)

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

      a[i][j]=read();

    for(int i=;i<=n;i++)

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

      b[i][j]=read();

    for(int i=n;i>=;i--){

        for(int k=;k<=n-i+;k++){

            for(int p=;p<=n-i+;p++){

                for(int q=;q<=n-i+;q++){

                    for(int y=;y<=n-i+;y++){

                        bool flag=true;

                        for(int j=;j<i;j++){

                            for(int l=;l<i;l++){

                                if(a[k+j][p+l]!=b[q+j][y+l]){

                                    flag=false;

                                    break;

                                }

                            }

                            if(flag==false)break;

                        }

                        if(flag){

                            printf("%d\n",i);

                            return ;

                        }

                    }

                }

            }

        }

    }

    return ;

}

巴特西