动态规划+单调栈。

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int l[N][N],r[N][N],h[N][N],a[N][N];
int main(){
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			l[i][j]=r[i][j]=j;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			h[i][j]=1;
	for(int i=1;i<=n;i++)
		for(int j=2;j<=m;j++)
			if(a[i][j]!=a[i][j-1])
				l[i][j]=l[i][j-1];
	for(int i=1;i<=n;i++)
		for(int j=m-1;j>=1;j--)
			if(a[i][j]!=a[i][j+1])
				r[i][j]=r[i][j+1];
	int ans1=0,ans2=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i>1&&(a[i][j]!=a[i-1][j])){
				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;
			}
			int siz=(r[i][j]-l[i][j]+1);
			int high=h[i][j];
			ans1=max(ans1,min(siz*siz,high*high));
			ans2=max(ans2,siz*high);
		}
	}
	printf("%d\n%d",ans1,ans2);
	return 0;
}