题目

link

题解

悬线法

正方形最大面积可以统计最大变成的平方

最大边长等于min(r[i][j] - l[i][j] + 1, h[i][j])

锅

当i==1时候l与r数组不要更新。。。。。

代码

#include<bits/stdc++.h>

using namespace std;
const int N = 2100;
int M[N][N];
int zhuan[N][N];
int n, m;
int h[N][N], l[N][N], r[N][N];
int main()
{
// 	freopen("in.in", "r", stdin);
// 	freopen("out.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= m;j++)
		{
			cin >> M[i][j];
			h[i][j] = 1;
			l[i][j] = r[i][j] = j;
		}
	}

	for(int i = 2;i <= n;i++)
	{
		for(int j = 1;j <= m;j++)
		{
			if(M[i - 1][j] != M[i][j])
			{
				h[i][j] = h[i - 1][j] + 1;
			}
		}
	}

	for(int i = 1;i <= n;i++)
	{
		for(int j = 2;j <= m;j++)
		{
			if(M[i][j - 1] != M[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(M[i][j + 1] != M[i][j])
			{
				r[i][j] = r[i][j + 1];
			}
		}
	}
	int maxsquare = 0;
	int maxlen = 0;
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= m;j++)
		{
			if(M[i - 1][j] != M[i][j])
			{
				if(i == 1) continue;
				l[i][j] = max(l[i][j], l[i - 1][j]);
				r[i][j] = min(r[i][j], r[i - 1][j]);
			}

			int b = min(r[i][j] - l[i][j] + 1, h[i][j]);
			maxlen = max(maxlen, b * b);
			maxsquare = max(maxsquare, (r[i][j] - l[i][j] + 1) * h[i][j]);
		}
	}
	cout << maxlen << endl;
	cout << maxsquare << endl;

	return 0;
}