首先了解一下悬线法：《浅谈用极大化思想解决最大子矩阵问题》
对于这道题，障碍点就是与当前点颜色相同的点，其他就照着模板做就好。
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> using namespace std; int n,m,bd[2010][2010],l[2010][2010],r[2010][2010],ht[2010][2010]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&bd[i][j]); l[i][j]=j;r[i][j]=j;ht[i][j]=1; //给悬线ij赋初值 } for(int i=1;i<=n;i++) for(int j=2;j<=m;j++) if(bd[i][j]!=bd[i][j-1]) l[i][j]=l[i][j-1]; //悬线ij可以向左延伸 for(int i=1;i<=n;i++) for(int j=m-1;j>=1;j--) if(bd[i][j]!=bd[i][j+1]) r[i][j]=r[i][j+1]; //悬线ij向右延伸 for(int i=2;i<=n;i++) for(int j=1;j<=m;j++) if(bd[i][j]!=bd[i-1][j]) { ht[i][j]=ht[i-1][j]+1; //悬线ij向上延伸 l[i][j]=max(l[i][j],l[i-1][j]); //悬线ij收缩左区间 r[i][j]=min(r[i][j],r[i-1][j]); //收缩右区间 } int ans1=0,ans2=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { int a=r[i][j]-l[i][j]+1,b=ht[i][j]; //悬线ij对应矩形宽为悬线ij左右延伸的距离，高为ij向上延伸距离 ans1=max(ans1,min(a,b)*min(a,b)); //对应正方形面积 ans2=max(ans2,a*b); //矩形面积 } printf("%d %d ",ans1,ans2); return 0; }