这道题目如果做过最大正方形的就会比较简单，可是我却完全不会，这道题目只是把对角线的转移改为了是 \(1\) 情况下的转移，然后在从右上多做一遍。
具体思路见这里
#include<bits/stdc++.h>
using namespace std;
const int N=2501;
short int f[N][N],b[N][N],c[N][N];
bool a[N][N];
int n,m,maxx;
inline int max(int x,int y) {return x>y ? x:y;}
inline int min(int x,int y) {return x<y ? x:y;}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
scanf("%d",a[i]+j);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
if (!a[i][j])
{
b[i][j]=b[i][j-1]+1;
c[i][j]=c[i-1][j]+1;
}
if (a[i][j])
f[i][j]=min(f[i-1][j-1],min(b[i][j-1],c[i-1][j]))+1;
maxx=max(maxx,f[i][j]);
}
memset(f,0,sizeof(f));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
for (int i=1;i<=n;i++)
for (int j=m;j>=1;j--)
{
if (!a[i][j])
{
b[i][j]=b[i][j+1]+1;
c[i][j]=c[i-1][j]+1;
}
if (a[i][j])
f[i][j]=min(f[i-1][j+1],min(b[i][j+1],c[i-1][j]))+1;
maxx=max(maxx,f[i][j]);
}
printf("%d\n",maxx);
return 0;
}需要注意的是这题空间非常容易爆炸，因为如果全开 \(int\) 的话，必要的三个数组就有 \(70M\) 多，如果输入的数组再开 \(int\) 的话就可能炸了。所以因为最大数据不会超过\(2501\)可以使用 \(short\ int\) ，格式控制符为\(\%hd\)，字节数为 \(int\) 的一半。