题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char g[N][N];
int l[N],r[N],q[N];
int U[N],D[N],L[N],R[N];
int s[N][N];
int n,m;
void init()
{
memset(s,0,sizeof(s));
for(int i = 1;i <=n;i++)
{
for(int j = 1;j <=m; j ++)
{
if(g[i][j] == 'F')s[i][j] = s[i-1][j] + 1;
else s[i][j] = 0;
//cout << s[i][j] << ' ';
}
//cout << endl;
}
}
int get(int s1[],int lth)
{
int tt = 0;
memset(q,0,n);
memset(l,0,n);
memset(r,0,n);
q[0] = 0;
for(int i = 1;i <= lth; i ++)
{
while(tt&& s1[q[tt]] >= s1[i])tt--;
l[i] = q[tt];
q[++tt] = i;
}
tt = 0;
q[0] = lth+1;
for(int i = lth;i; i --)
{
while(tt&& s1[q[tt]] >= s1[i])tt--;
r[i] = q[tt];
q[++tt] = i;
}
int res = 0;
for(int i = 1;i <= lth; i ++)
{
res = max(res,s1[i]*(r[i] - l[i] - 1));
}
//cout << res << ' ';
return res;
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
{
char c;
cin >> c;
g[i][j] = c;
}
init();
int total_res = 0;
for(int i = 1;i <= n;i ++)
{
total_res = max(total_res,get(s[i],m));
}
cout << total_res * 3;
return 0;
}