問題#
解法#
悬線法
正方形の最大面積は最大の平方を統計できます
最大辺の長さは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;
}