题目链接:传送门
二维哈希枚举边长和两个正方形的两个端点复杂度不满n5n^5n5好吧差不多刚好卡过去
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<complex>#include<algorithm>#include<climits>#include<queue>#include<map>#include<set>#include<vector>#include<iomanip>#defineA51#defineB2010usingnamespacestd;typedeflonglongll;constintbase1=13;constintbase2=19;intn,a[A][A],b[A][A],ans;llha[A][A],hb[A][A];llf1[A]={1},f2[A]={1};intmain(intargc,charconst*argv[]){cin>>n;for(inti=1;i<51;i++)f1[i]=f1[i-1]*base1,f2[i]=f2[i-1]*base2;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)scanf("%d",&a[i][j]),ha[i][j]=a[i][j]+ha[i-1][j]*base1;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)ha[i][j]+=ha[i][j-1]*base2;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)scanf("%d",&b[i][j]),hb[i][j]=b[i][j]+hb[i-1][j]*base1;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)hb[i][j]+=hb[i][j-1]*base2;for(intlen=1;len<n;len++)for(inti=len;i<=n;i++)for(intj=len;j<=n;j++)for(intt=len;t<=n;t++)for(into=len;o<=n;o++){if(a[i][j]!=b[t][o])continue;llhasha=ha[i][j]-ha[i-len][j]*f1[len]-ha[i][j-len]*f2[len]+ha[i-len][j-len]*f1[len]*f2[len];llhashb=hb[t][o]-hb[t-len][o]*f1[len]-hb[t][o-len]*f2[len]+hb[t-len][o-len]*f1[len]*f2[len];if(hasha==hashb)ans=max(ans,len);}cout<<ans<<endl;}