https://www.luogu.org/problemnew/show/P1169

C++版本一

悬线法

以l[i][j]表示(i,j)这个点向左走碰到的第一个障碍，r[i][j]表示向右走碰到的第一个障碍。 
h[i][j]即所谓的悬线，表示向上走最多能走几步，那么有一个显然的结论，最后的这个答案，一定是一条悬线向左右两边扩展得到，不然的话完全可以再向上走一步。 
L[i][j]表示我(i,j)的这条悬线向左边碰到的第一个障碍，R[i][j]表示向右边碰到的第一个障碍，那么我最后的这个答案就是(R[i][j]−L[i][j]−1)∗h[i][j]。 

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=2000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans1,ans2,cnt,flag,temp;
int a[N][N];
int high[N][N];
char str;
int l[N][N],r[N][N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d%d",&n,&m);
    //scanf("%d",&t);
    //while(t--){}
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
            l[i][j]=r[i][j]=j;
            high[i][j]=1;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=2;j<=m;j++){
            if(a[i][j-1]!=a[i][j]){
                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+1]!=a[i][j]){
                r[i][j]=r[i][j+1];
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i>1&&a[i-1][j]!=a[i][j]){
                l[i][j]=max(l[i][j],l[i-1][j]);
                r[i][j]=min(r[i][j],r[i-1][j]);
                high[i][j]=high[i-1][j]+1;
            }
            int a=r[i][j]-l[i][j]+1;
            int b=high[i][j];
            int minl=min(a,b);
            ans1=max(ans1,minl*minl);//正方形
            ans2=max(ans2,a*b);//长方形
        }
    }
    cout << ans1 << endl;
    cout << ans2 << endl;
    //cout << "Hello world!" << endl;
    return 0;
}