题意大概就是要从一个n * m的矩阵当中，求出一个主对角线或者副对角线都是1，其它地方都是0的最大正方形，并输出它的边长。
最暴力的方法应该就是枚举，对于任何一点(i , j)，枚举它作为正方形的左上顶点/右上顶点时，能够构成的合法的最大正方形，怎么判断这个正方形是合法的呢？最简单的应当就是分别判断主副对角线是否都为1，再判断其余部分是否都为0。但是这么枚举的话，多半是会TLE的，所以我们要考虑优化。

我们可以用DP进行优化：
dp[i,j]表示以(i , j)为左上顶点/右上顶点时能构成的最大正方形的边长。
显然如果map[i,j]=0，dp[i,j]=0.
为了方便，我们考虑从下往上，从右到左扫描整个矩阵。
初始化：dp[n,1-m] = map[n,1-m]==1? 1:0；
状态转移有点难讲清，可以看看代码中的解释，然后自己写一下样例理解理解。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=2505;
int dp[maxn][maxn],map[maxn][maxn];

inline void read(int &ret)
{
	char c;
	while((c=getchar())&&(c>'9'||c<'0'));
	ret=0;
	while(c>='0'&&c<='9')	ret=ret*10+c-'0', c=getchar();
}

int main()
{
	int n,m;
	read(n);	read(m);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			read(map[i][j]);
	int ans=0;
	for(int i=m;i>=1;--i)	
	{
		dp[n][i]= map[n][i]==1? 1:0;
		ans=max(ans,dp[n][i]);
	}
	for(int i=1;i<=n;++i)	dp[i][0]=dp[i][m+1]=0;	//为了方便，将(1-n,0) (1-n,m+1)都初始为0
	for(int i=n-1;i>=1;--i)
	{
		for(int j=m;j>=1;--j)
		{
			if(!map[i][j])	dp[i][j]=0;
			else
			{
				int mi1=0,mi2=0;	//mi1记录(i,j)作为左上顶点时，能够扩张的最大边长，同理mi2记录右上顶点
				if(dp[i+1][j+1])	//如果dp[i+1,j+1]!=0
				{
					int temp=dp[i+1][j+1];	//temp用于更新能够扩张的最大边长
					for(int k=j+1;k<=m&&k<=j+temp;++k)	//从左往右扫描，如果扫到1就更新temp并终止
						if(map[i][k])
						{
							temp=k-1-j;
							break;
						}
					for(int k=i+1;k<=n&&k<=i+temp;++k)	//同理，从上往下扫描
						if(map[k][j])
						{
							temp=k-1-i;
							break;
						}
					mi1=temp;	//将temp的值赋给mi1
				}
				if(dp[i+1][j-1])	//同理
				{
					int temp=dp[i+1][j-1];
					for(int k=j-1;k>=1&&k>=j-temp;--k)
						if(map[i][k])
						{
							temp=j-k-1;
							break;
						}
					for(int k=i+1;k<=n&&k<=i+temp;++k)
						if(map[k][j])
						{
							temp=k-i-1;
							break;
						}
					mi2=temp;
				}
				dp[i][j]=max(mi1,mi2)+1;
				ans=max(ans,dp[i][j]);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

PS：其实这个DP是自己打个表，手推出来的。时间复杂度看似n³，但其实只有n²+，所以还是阔以的。