杜老师的演唱会

题目背景
dls的梦想能够自己开一场演唱会，为了实现dls的梦想，毛老师为他筹备演唱会的场地忙得焦头烂额。

演唱会的备选场地可以看成是一块 \(n×m\) 的网格，dls演唱会的场地比较特殊，需要为一块金字塔形状的等腰三角形，且必须保证底边是沿着水平方向的。（在平面上面一定是一个金字塔形状，且必须保证塔尖朝上）。

举个例子：

如下图，分别是高度为1、2、3、5的金字塔型等腰三角形，面积大小分别为1，4，9，25。（空白部分可以是任意字符）：

1      1       1         1
      111     111       111
             11111     11111
                      1111111    
                     111111111 

备选场地中有一些“沼泽”（用0表示）和一些“平地”（用1表示），演唱会场地只能建在平地上。

dls希望他的演唱会尽量大，所以毛老师希望你在这块被选场地中找出最大的金字塔型等腰三角形，并告诉他所覆盖的面积大小。

输入格式
第一行包括两个正整数$ n,m$，描述备选场地的长，宽。

之后 \(n\) 行每行包括 \(m\) 个 01 的字符（中间没有空格），描述一个01矩阵，表示备选场地的“沼泽”“平地”的情况。

输出格式
仅输出一行一个正整数，表示最大的面积。

样例
input

5 8
01111110
11111111
11101111
11111111
11101110

output

9

explanation

01111110
11111X11
1110XXX1
111XXXXX
11101110

X部分为最大的金字塔型等腰三角形。
时空限制
时间限制：1s

空间限制：256M

对于 20% 的数据，满足 \(n≤5,m≤10\)。

对于 40% 的数据，满足 \(n≤50,m≤100\)。

对于 60% 的数据，满足 \(n≤400,m≤800\)。

对于 100% 的数据，满足 \(n≤1000,m≤2000\)。

定义\(dp_{i,j}\)为以\((i,j)\)为三角形塔尖时三角形的最高高度。
那么\(dp_{i,j}\)如果等于\(k\),那么\(dp_{i+1,j-1},dp_{i+1,j},dp_{i+1,j+1}\)都等于\(k-1\)。换句话说,如果\(a_{i,j}\)为1，\(dp_{i,j}=\max{dp_{i+1,j-1},dp_{i+1,j},dp_{i+1,j+1}}\),我们把\(i\)从大到小循环,dp即可。

#include 
#include
using namespace std;
const int N=2005;
int n,m,dp[N][N],ans;
char c;
int main()
{
	scanf("%d%d",&n,&m),getchar();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			c=getchar();
			if(c=='1')
				dp[i][j]=1;
		}
		getchar();
	}
	for(int i=n-1;i>=1;i--)
	{
		for(int j=1;j<=m;j++)
		{
			if(dp[i][j]&&dp[i+1][j])
				dp[i][j]=max(dp[i][j],min(dp[i+1][j-1],dp[i+1][j+1])+1);
			ans=max(ans,dp[i][j]);
		}
	}
	printf("%lld",1LL*ans*ans);
	return 0;
}