题目链接
题解
考虑把黑白相间的棋盘转换成同一个颜色，方便之后的操作。可以通过行标与列标之和的奇偶判断是否应该染上相反的颜色
那么黑格行列奇偶性相同，白格不同;白格行列奇偶性相同，黑格不同
把第一种情况的赋1，属于第二种情况的赋0
统计最大的1或0正方形或矩形
代码
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using std::min;
using std::max;
const int MAXN=2001;
int a[MAXN][MAXN];
int read(int & n) {
int flag=0,x=0;char c='/';
while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
while(c>='0'&&c<='9')x=x*10+(c-48),c=getchar();
if(flag)n=-x;else n=x;
}
int n,m;
int dps[MAXN][MAXN];
int dpr1[MAXN][MAXN];
int dpr2[MAXN][MAXN];
int ans1,ans2;
void find_1() {
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
dps[i][j]=1;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++) {
if(a[i][j]==a[i][j-1]&&a[i][j]==a[i-1][j-1]&&a[i][j]==a[i-1][j]) {
dps[i][j]=min(min(dps[i-1][j-1],dps[i][j-1]),min(dps[i-1][j-1],dps[i-1][j]))+1;
ans1=max(dps[i][j],ans1);
}
}
printf("%d
",ans1*ans1);
}
void find_2() {
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
dpr1[i][j]=dpr2[i][j]=1;
for(int i=1;i<n;i++)
for(int j=0;j<m;j++)
if(a[i][j]==a[i-1][j])
dpr1[i][j]=max(dpr1[i][j],dpr1[i-1][j]+1);
for(int i=n-2;i>=0;i--)
for(int j=0;j<m;j++)
if(a[i][j]==a[i+1][j])
dpr2[i][j]=max(dpr2[i][j],dpr2[i+1][j]+1);
ans2=1;
for(int i=0;i<n;i++) {
int maxup=dpr1[i][0];
int maxdown=dpr2[i][0];
int maxlong=0;
for(int j=0;j<m;j++) {
ans2=max(ans2,(j-maxlong+1)*(maxup+maxdown-1));
if(j==m-1)
break;
if(a[i][j]!=a[i][j+1]) {
maxlong=j+1;
maxup=dpr1[i][j+1];
maxdown=dpr2[i][j+1];
}
else {
maxup=min(maxup,dpr1[i][j+1]);
maxdown=min(maxdown,dpr2[i][j+1]);
}
}
}
printf("%d
",ans2);
}
int main() {
read(n);read(m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++) {
read(a[i][j]);
a[i][j]^=(i^j)&1;
}
find_1();
find_2();
return 0;
}