#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
struct node{
    int x,y,m;
};
int n,dp[N][N];
bool a[N][N],v[N][N];
int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,-1,1};
bool bfs(int h){
    queue<node>q;
    q.push({1,1,dp[1][1]});
    memset(v,0,sizeof(v));
    v[1][1]=1;
    while(!q.empty()){
        node bot=q.front();q.pop();
        int xx=bot.x,yy=bot.y,c=bot.m;
        if(xx==n&&yy==n)return 1;
        for(int i=1;i<=4;i++){
            int ex=xx+dx[i],ey=yy+dy[i];
            if(ex<1||ex>n||ey<1||ey>n||v[ex][ey]||dp[ex][ey]<h)
                continue;
            q.push({ex,ey,min(c,dp[ex][ey])});
            v[ex][ey]=1;
        }
    }
    return 0;
}
void search(int l,int r){
    if(l>=r){
        if(l%2==0)l--;
        printf("%d\n",l);
        return;
    }
    int mid=(l+r)/2;
    if(bfs(mid))search(mid,r);
    else search(l,mid-1);
    return;
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(!a[i][j]) 
                dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
    if(!bfs(1))printf("%d\n",-1);
    else search(1,2*n);
    return 0;
}

$30\%$ 的数据满足 $n \leq 10$

$60\%$ 的数据满足 $n \leq 2000$

$100\%$ 的数据满足 $n \leq 5000$

且提示中说放过了 $\Theta(n^2 \log n)$ 做法，只拿 27pts 我不是很认可。

时限甚至 5s。