BZOJ原题链接
洛谷原题链接
设\(L[i][j],R[i][j],H[i][j]\)表示点\((i,j)\)向左、右、上尽量拓展的左端点、右端点、上端点的坐标。
\(L,R\)直接初始化好，\(H\)则全部为\(1\)。
扫过整个矩阵，对于每个点，尽量去拓展上端点，并更新\(L[i][j] = \max\{ L[i][j], L[i - 1][j] \}, R[i][j] = \min\{ R[i][j], R[i - 1][j] \}, H[i][j] = H[i - 1][j] + 1\)，然后尝试去更新答案即可。
不得不吐糟一句，某谷的数据是真的水。
#include<cstdio>
using namespace std;
const int N = 2010;
int a[N][N], L[N][N], R[N][N], H[N][N];
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
inline int maxn(int x, int y)
{
return x > y ? x : y;
}
inline int minn(int x, int y)
{
return x < y ? x : y;
}
inline int squ(int x)
{
return x * x;
}
int main()
{
int i, j, n, m, l, sq = 1, rec = 1;
n = re();
m = re();
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
a[i][j] = re();
L[i][j] = R[i][j] = j;
H[i][j] = 1;
}
for (i = 1; i <= n; i++)
for (j = 2; j <= m; j++)
if (a[i][j] ^ a[i][j - 1])
L[i][j] = L[i][j - 1];
for (i = 1; i <= n; i++)
for (j = m - 1; j; j--)
if (a[i][j] ^ a[i][j + 1])
R[i][j] = R[i][j + 1];
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
if (i > 1 && a[i][j] ^ a[i - 1][j])
{
L[i][j] = maxn(L[i][j], L[i - 1][j]);
R[i][j] = minn(R[i][j], R[i - 1][j]);
H[i][j] = H[i - 1][j] + 1;
}
l = R[i][j] - L[i][j] + 1;
sq = maxn(sq, squ(minn(l, H[i][j])));
rec = maxn(rec, l * H[i][j]);
}
printf("%d\n%d", sq, rec);
return 0;
}