我是一个既没想到dp又没想到根据坐标奇偶性取反的脑回路有些奇怪的蒟蒻
个人脑洞:
从第一行到第n行扫一遍,维护h数组表示从当前格子往上能延伸到的黑白相间的线段(有一条边长为1的矩形)的最长长度
我们可将当前行分为若干条线段,满足每条线段是最长的黑白相间的线段(不能再向左右延伸)
对于每条线段,结合h数组,我们不难发现我们得到了一排高矮不一的长条状的矩形
是不是很熟悉?用单调栈扫一遍即可
如果遇到颜色与上一个相同的格子,就把整个栈弹出来
注意正方形可以在数矩形的时候顺便数出来
```
#include<cstdio>
#include<iostream>
#include<cstring>
#define X (h[stack[top]])//矩形的宽
#define Y (cur-stack[top-1]-1)//矩形的长
#define Z (min(X,Y))//正方形的边长
using namespace std;
int n,m,top,cur,ans1,ans2,stack[2010],map[2010][2010],h[2010];
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j) scanf("%d",&map[i][j]);
for (int j=1;j<=n;++j){
for (int i=1;i<=m;++i)
if (j>1&&map[j][i]!=map[j-1][i]) ++h[i];
else h[i]=1;
cur=1;
while (cur<=m){
stack[0]=cur-1;stack[top=1]=cur++;
while (cur<=m&&(map[j][cur]!=map[j][cur-1])){
while (top&&h[stack[top]]>h[cur])
ans1=max(ans1,Z*Z),ans2=max(ans2,X*Y),--top;
stack[++top]=cur++;
}
while (top) ans1=max(ans1,Z*Z),ans2=max(ans2,X*Y),--top;
}
}
printf("%d\n%d\n",ans1,ans2);
return 0;
}
```