Description
给一个01矩阵， 求出最大的01交错的正方形和最大的01交错的矩阵
Solution
用动态规划求出最大的正方形， 用单调栈求出最大的矩阵。
在这里仅介绍求出最大正方形（求最大矩阵 = 单调栈裸题 传送门 ： 不会单调栈的同学可以去学
定义数组$f[ i ][ j ]$ 为以$(i, j) $为右下角的正方形的边长
$up[ i ][ j ]$ 表示从点$(i, j)$往上 $01$交错的长度
$lef[ i ][ j ]$ 表示从点$(i, j)$往右$01$交错的长度
当 $a[ i ][ j ] != a[i - 1][j - 1]$时才可由上一个正方形继续拓展， 否则长度 $f[ i ][ j ] = 1$
于是有转移方程：
$f[ i ][ j ] = 1$ $a[ i ][ j ] == a[i - 1][j - 1]$
$f[ i ][ j ] = min(f[ i - 1][ j - 1] + 1, lef[ i ][ j ], up[ i ][ j ])$ $ a[ i ][ j ] != a[i - 1][ j ]$
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
#define rep(i,a,b) for(register int i = (a); i <= (b); i++)
#define per(i,a,b) for(register int i = (a); i >= (b); --i)
#define R register
using namespace std; const int N = 3e3; int n, m, a[N][N], pre[N], nxt[N], h[N], ans2;
int lf[N][N], u[N][N], f[N][N], ans1;
int st[N], tp; int read() {
int X = , p = ; char c = getchar();
for(; c > '' || c < ''; c = getchar()) if(c == '-') p = -;
for(; c >= '' && c <= ''; c = getchar()) X = X * + c - '';
return X * p;
} void work(int x) {
rep(i, , m) pre[i] = , nxt[i] = m + ;
rep(i, , m)
if(a[x][i] != a[x - ][i]) h[i]++;
else h[i] = ;
tp = ;
rep(i, , m) {
int pr = ;
while(tp) {
if(h[st[tp]] >= h[i]) tp--;
else {
pr = st[tp]; break;
}
}
pre[i] = pr;
st[++tp] = i;
}
tp = ;
per(i, m, ) {
int nt = m + ;
while(tp) {
if(h[st[tp]] >= h[i]) tp--;
else {
nt = st[tp]; break;
}
}
nxt[i] = nt;
st[++tp] = i;
}
rep(i, , m) {
int nt = nxt[i], pr = pre[i];
rep(j, i + , nt)
if(a[x][j] == a[x][j - ]) {nt = j; break;}
per(j, i - , pr)
if(a[x][j] == a[x][j + ]) {pr = j; break;}
ans2 = max(ans2, (nt - pr - ) * h[i]);
}
} int main()
{
n = rd; m = rd;
memset(a, -, sizeof(a));
rep(i, , n) rep(j, , m) a[i][j] = rd;
rep(i, , n) rep(j, , m) {
f[i][j] = ;
if(a[i][j] != a[i][j - ])
lf[i][j] = lf[i][j - ] + ;
else lf[i][j] = ;
if(a[i][j] != a[i - ][j])
u[i][j] = u[i - ][j] + ;
else u[i][j] = ;
if(a[i][j] != a[i - ][j - ]) continue;
f[i][j] = min(u[i][j], lf[i][j]);
f[i][j] = min(f[i - ][j - ] + , f[i][j]);
ans1 = max(ans1, f[i][j]);
}
printf("%d\n", ans1 * ans1);
rep(i, , n) work(i);
printf("%d\n", ans2);
}