题目描述

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

2

HINT

子矩阵：
5 6
8 9
为两个地图的最大公共矩阵
约定：
n<=50

题目分析

二分+二维hash裸题
随便搞搞就好了

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
typedef unsigned long long ull; 
int n;
ull mp[60][60],mp2[60][60];
ull base=2333,base2=23333;
ull hsh[60][60],hsh2[60][60];
ull pw[60],po[60];
void init()
{
    pw[0]=po[0]=1;
    for(int i=1;i<=50;i++)
        pw[i]=pw[i-1]*base,po[i]=po[i-1]*base2;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            hsh[i][j]=hsh[i-1][j]*base+mp[i][j];
            hsh2[i][j]=hsh2[i-1][j]*base+mp2[i][j];
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            hsh[i][j]=hsh[i][j-1]*base2+hsh[i][j];
            hsh2[i][j]=hsh2[i][j-1]*base2+hsh2[i][j];
        }
}   
map<ull,int>s; 
int check(int mid)
{       
    s.clear();
    for(int i=mid;i<=n;i++)
        for(int j=mid;j<=n;j++)
        {
            ull tmp=hsh[i][j];
            tmp-=hsh[i-mid][j]*pw[mid];
            tmp-=hsh[i][j-mid]*po[mid];
            tmp+=hsh[i-mid][j-mid]*pw[mid]*po[mid];
            s[tmp]=1;
        }
    for(int i=mid;i<=n;i++)
        for(int j=mid;j<=n;j++)
        {
            ull tmp=hsh2[i][j];
            tmp-=hsh2[i-mid][j]*pw[mid];
            tmp-=hsh2[i][j-mid]*po[mid];
            tmp+=hsh2[i-mid][j-mid]*pw[mid]*po[mid];
            if(s[tmp]) return 1;
        }
    return 0;
}   
int main()
{   
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) scanf("%llu",&mp[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) scanf("%llu",&mp2[i][j]);            
    init();
    int l=1,r=n,mid,ans=0;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid)) l=mid+1,ans=mid;
        else r=mid;
    }
    printf("%d",ans);
    return 0;
}