Luogu

分析

在原方阵的基础上构造出 $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;
}