分析
在原方阵的基础上构造出 $6$ 个方阵，分别为原方阵沿 $4$ 条轴对称之后的方阵、旋转 $90^\circ$ 后的方阵、旋转 $180^\circ$ 后的方阵。然后对这 $7$ 个方阵做一遍哈希。
现在一个暴力做法是，枚举边长和左上角的坐标，然后利用哈希判断它是否满足某些条件。这样子是 $\mathcal{O}(n^3)$ 的，并跑不过。
考虑到如果存在一个边长为 $k$ 的方阵满足某些条件，那么一定存在一个边长为 $k-2$ 的方阵同样满足这些条件。于是将枚举边长替换为对奇数和偶数各二分一遍即可。时间复杂度 $\mathcal{O}(n^2\log n)$。
代码中用了一些技巧来缩小代码量。
代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
typedef unsigned long long ull;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=500+10;
const ull BASE1=19260817,BASE2=19491001;
int n; char s[N][N];
ull pw1[N],pw2[N];
ull h[8][N][N];
inline void init_hash() {
pw1[0]=1; for (re int i=1;i<=n;++i) pw1[i]=pw1[i-1]*BASE1;
pw2[0]=1; for (re int i=1;i<=n;++i) pw2[i]=pw2[i-1]*BASE2;
for (re int i=1;i<=n;++i)
for (re int j=1;j<=n;++j) {
h[1][i][j]=s[i][j];
h[2][j][i]=s[i][j];
h[3][n-j+1][n-i+1]=s[i][j];
h[4][n-i+1][j]=s[i][j];
h[5][i][n-j+1]=s[i][j];
h[6][j][n-i+1]=s[i][j];
h[7][n-i+1][n-j+1]=s[i][j];
}
for (re int k=1;k<=7;++k)
for (re int i=1;i<=n;++i)
for (re int j=1;j<=n;++j) {
h[k][i][j]=h[k][i-1][j]*BASE1+h[k][i][j-1]*BASE2
-h[k][i-1][j-1]*BASE1*BASE2+h[k][i][j];
}
}
inline ull gethash(int id,int lx,int ly,int rx,int ry) {
int l=rx-lx+1;
return h[id][rx][ry]-h[id][lx-1][ry]*pw1[l]-h[id][rx][ly-1]*pw2[l]
+h[id][lx-1][ly-1]*pw1[l]*pw2[l];
}
inline int check_axis(int lx,int ly,int rx,int ry) {
return gethash(1,lx,ly,rx,ry)==gethash(2,ly,lx,ry,rx)
||gethash(1,lx,ly,rx,ry)==gethash(3,n-ry+1,n-rx+1,n-ly+1,n-lx+1)
||gethash(1,lx,ly,rx,ry)==gethash(4,n-rx+1,ly,n-lx+1,ry)
||gethash(1,lx,ly,rx,ry)==gethash(5,lx,n-ry+1,rx,n-ly+1);
}
inline int check_90(int lx,int ly,int rx,int ry) {
return gethash(1,lx,ly,rx,ry)==gethash(6,ly,n-rx+1,ry,n-lx+1);
}
inline int check_180(int lx,int ly,int rx,int ry) {
return gethash(1,lx,ly,rx,ry)==gethash(7,n-rx+1,n-ry+1,n-lx+1,n-ly+1);
}
inline int check_8(int lx,int ly,int rx,int ry) {
return check_90(lx,ly,rx,ry)&&check_axis(lx,ly,rx,ry);
}
inline int check_4(int lx,int ly,int rx,int ry) {
return check_180(lx,ly,rx,ry)&&check_axis(lx,ly,rx,ry);
}
template<typename T>
inline int check(T f,int l) {
for (re int x=1;x+l-1<=n;++x)
for (re int y=1;y+l-1<=n;++y)
if (f(x,y,x+l-1,y+l-1)) return 1;
return 0;
}
template<typename T>
inline int solve(T f) { int L,R,res=0;
L=0,R=(n-1)>>1;
while (L<R) {
int mid=(L+R+1)>>1;
if (check(f,mid<<1|1)) L=mid;
else R=mid-1;
}
res=max(res,L<<1|1);
L=1,R=n>>1;
while (L<R) {
int mid=(L+R+1)>>1;
if (check(f,mid<<1)) L=mid;
else R=mid-1;
}
res=max(res,L<<1);
return res;
}
int main() {
n=read();
for (re int i=1;i<=n;++i) scanf("%s",s[i]+1);
init_hash();
printf("%d ",solve(check_8));
printf("%d ",solve(check_90));
printf("%d ",solve(check_4));
printf("%d ",solve(check_180));
printf("%d\n",solve(check_axis));
return 0;
}