本文共 1917 字，大约阅读时间需要 6 分钟。

思路

这道题我没有经过太多思考，直接就写了 $O(n^4{\log }_{2}n)$ 的代码，
思路就是首先把两个矩阵的所有正方形hash一次，然后再暴力去枚举两个正方形随意两个右下角的点，
然后二分求最大边长看看hash值是否相等就好了。

代码

#include<algorithm>#include<iostream>#include<cstdio>#include<cmath>using namespace std;unsigned long long hasha[101][101],hashb[101][101];unsigned long long f1[100010],f2[100010];int n,ans;void ycl(){   	f1[0]=1ull,f2[0]=1ull;	for(int i=1; i<=n; i++)	   f1[i]=f1[i-1]*1000000007ull;	for(int i=1; i<=n; i++)	   f2[i]=f2[i-1]*1000000009ull;	for(int i=1; i<=n; i++)	 for(int j=1; j<=n; j++)	    hasha[i][j]+=hasha[i][j-1]*1000000007ull;	for(int i=1; i<=n; i++)	 for(int j=1; j<=n; j++)	    hasha[i][j]+=hasha[i-1][j]*1000000009ull;	for(int i=1; i<=n; i++)	 for(int j=1; j<=n; j++)	    hashb[i][j]+=hashb[i][j-1]*1000000007ull;	for(int i=1; i<=n; i++)	 for(int j=1; j<=n; j++)	    hashb[i][j]+=hashb[i-1][j]*1000000009ull;}bool check(int i,int j,int k,int w,int mid){       if(i-mid<0||j-mid<0||w-mid<0||k-mid<0)      return 0;    unsigned long long jsa=hasha[i][j]-hasha[i-mid][j]*f2[mid]-hasha[i][j-mid]*f1[mid]+hasha[i-mid][j-mid]*f1[mid]*f2[mid];    unsigned long long jsb=hashb[k][w]-hashb[k-mid][w]*f2[mid]-hashb[k][w-mid]*f1[mid]+hashb[k-mid][w-mid]*f1[mid]*f2[mid];//    if(i==3&&j==3&&k==2&&w==2&&mid==2)//      cout<<jsa<<" "<<jsb;    if(jsb==jsa)      return 1;    else      return 0;}int main(){   	cin>>n;	for(int i=1; i<=n; i++)	 for(int j=1; j<=n; j++)	    scanf("%d",&hasha[i][j]);	for(int i=1; i<=n; i++)	 for(int j=1; j<=n; j++)	    scanf("%d",&hashb[i][j]);	ycl();    for(int i=1; i<=n; i++)     for(int j=1; j<=n; j++)      for(int k=1; k<=n; k++)       for(int w=1; w<=n; w++)        {           	int l=0,r=n,mid=0;        	while(l<=r)        	 {           	 	mid=(l+r)>>1;        	 	if(check(i,j,k,w,mid))        	 	  {           	 	  	l=mid+1,ans=max(ans,mid);        	 	  	        	 	  }				 else        	 	  r=mid-1;			 }		}	cout<<ans;	return 0;}