悬线法+动态规划

在做本题之前, 我们先要接触一个东西叫悬线法
在悬线法中, 我们定义
$l[i][j]:l[i][j]:$ 表示 $(i,j)(i,j)$ 能够向左延伸的最远位置(就是记录的能够走的,最左边的纵坐标)
$r[i][j]:r[i][j]:$ 表示 $(i,j)(i,j)$ 能够向右延伸的最远位置(就是记录的能够走的,最右边的纵坐标)
$u[i][j]:u[i][j]:$ 表示 $(i,j)(i,j)$ 能够向上延伸的最大距离

#include<bits/stdc++.h>

using namespace std;

int n, m;
int g[2010][2010], l[2010][2010], r[2010][2010], u[2010][2010];
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> m;

	for(int i = 1; i <= n; i ++ ) 
		for(int j = 1; j <= m; j ++ )
		{
			cin >> g[i][j];
			l[i][j] = r[i][j] = j; //初始化为当前位置
			u[i][j] = 1; //初始化距离为 1
		}
	for(int i = 1; i <= n; i ++ )
		for(int j = 2; j <= m; j ++ )
		{
			if(g[i][j] != g[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(g[i][j] != g[i][j + 1]) //如果能够向右扩展
				r[i][j] = r[i][j + 1];
		}

	int s = 1, dist = 1;
	for(int i = 1; i <= n; i ++ ) //枚举端点
		for(int j = 1; j <= m; j ++ )
		{
			if(g[i][j] != g[i - 1][j] && i != 1) //如果能够向上扩展, i != 1是因为1不能向上扩展了
			{
				u[i][j] = u[i - 1][j] + 1;
				l[i][j] = max(l[i][j], l[i - 1][j]); //记录最右边的位置
				r[i][j] = min(r[i][j], r[i - 1][j]); //记录最左边的位置
			}
			dist = max(dist, min(u[i][j], r[i][j] - l[i][j] + 1)); //正方形
			s = max(s, u[i][j] * (r[i][j] - l[i][j] + 1)); //矩形
		}
	cout << dist * dist << '\n';
	cout << s << '\n';
}