P4398 [JSOI2008]Blue Mary的战役地图 矩阵哈希

#include<cstdio>
#include<map>
#include<iostream>
#define ull unsigned long long
#define R register int
using namespace std;
inline int g() {
    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch==‘-‘?-1:fix;
    do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
} const int B=11,B2=13,N=51;
map<ull,bool> mp;
int n;
ull p[N],p2[N],a[N][N];
inline ull calc(int x,int y,int l) {return a[x][y]-a[x-l][y]*p2[l]-a[x][y-l]*p[l]+a[x-l][y-l]*p[l]*p2[l];}
signed main() {
    n=g(); p[0]=p2[0]=1; for(R i=1;i<=n;++i) p[i]=p[i-1]*B; for(R i=1;i<=n;++i) p2[i]=p2[i-1]*B2;
    for(R i=1;i<=n;++i) for(R j=1;j<=n;++j) a[i][j]=g();
    for(R i=1;i<=n;++i) for(R j=1;j<=n;++j) a[i][j]=a[i][j-1]*B+a[i][j];
    for(R i=1;i<=n;++i) for(R j=1;j<=n;++j) a[i][j]=a[i-1][j]*B2+a[i][j];
    for(R l=0;l<n;++l) for(R i=l;i<=n;++i) for(R j=l;j<=n;++j) mp[calc(i,j,l)]=true;
    for(R i=1;i<=n;++i) for(R j=1;j<=n;++j) a[i][j]=g();
    for(R i=1;i<=n;++i) for(R j=1;j<=n;++j) a[i][j]=a[i][j-1]*B+a[i][j];
    for(R i=1;i<=n;++i) for(R j=1;j<=n;++j) a[i][j]=a[i-1][j]*B2+a[i][j];
    for(R l=n;l;--l) for(R i=l;i<=n;++i) for(R j=l;j<=n;++j) if(mp.find(calc(i,j,l))!=mp.end()) {printf("%d\n",l); return 0;}
}