題目#
題解#
懸線法
正方形最大面積可以統計最大變成的平方
最大邊長等於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;
}