转载请注明出处谢谢：http://blog.csdn.net/vmurder/article/details/42886393
题解：
嗯，这个图确实不太好做，
但是我们可以把它转化成求全是1/0的子矩阵问题。
就是把行列奇偶性相同的点01取反，然后就好了（这是显然的，需要证明的留言）。
然后就是求最大子矩阵了。
至于正方形？求子矩阵时顺带求了，就是那个ans1，
这个显然，因为我们枚举了每一个点的延展性，所以不会漏掉任何可能性。
这么说吧，假设有一个正方形没有考虑到，那么它的长或者宽一定是一个极大值，那么就一定会出现在某个我们计算的矩形中！
然后怎么求最大01子矩阵见上一篇博客http://blog.csdn.net/vmurder/article/details/42884845
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 2020
#define inf 0x3f3f3f3f
using namespace std;
int map[N][N];
int l[N],r[N],d[N];
int n,m,ans1,ans2;
int main()
{
freopen("test.in","r",stdin);
int i,j,k,t;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)for(j=1;j<=m;j++)
{
scanf("%d",&map[i][j]);
if((i+j&1)==0)map[i][j]=(!map[i][j]);
}
// d[0]=d[m+1]=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
l[j]=r[j]=j;
if(map[i][j])d[j]++;
else d[j]=0;
}
for(j=1;j<=m;j++)if(d[j])while(d[l[j]-1]>=d[j])l[j]=l[l[j]-1];
for(j=m;j>=1;j--)if(d[j])while(d[r[j]+1]>=d[j])r[j]=r[r[j]+1];
for(j=1;j<=m;j++)
{
k=r[j]-l[j]+1;
t=min(k,d[j]);
ans1=max(ans1,t*t);
ans2=max(ans2,k*d[j]);
}
}
memset(d,0,sizeof d);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
l[j]=r[j]=j;
if(!map[i][j])d[j]++;
else d[j]=0;
}
for(j=1;j<=m;j++)if(d[j])while(d[l[j]-1]>=d[j])l[j]=l[l[j]-1];
for(j=m;j>=1;j--)if(d[j])while(d[r[j]+1]>=d[j])r[j]=r[r[j]+1];
for(j=1;j<=m;j++)
{
k=r[j]-l[j]+1;
t=min(k,d[j]);
ans1=max(ans1,t*t);
ans2=max(ans2,k*d[j]);
}
}
printf("%d\n%d\n",ans1,ans2);
return 0;
}