AcWing 152. 城市游戏
原题链接
中等
作者:
wjie
,
2020-07-29 23:51:40
,
所有人可见
,
阅读 410
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e3 + 5;
char arr[N][N];
int n, m, height[N][N];
int lef[N], rig[N];
int func(int row)
{
height[row][0] = height[row][m+1] = -1;
vector<int> temp;
temp.push_back(0);
for (int i = 1; i <= m; ++i)
{
while (height[row][temp.back()] >= height[row][i]) temp.pop_back();
lef[i] = temp.back();
temp.push_back(i);
}
temp.clear();
temp.push_back(m+1);
for (int i = m; i >= 1; --i)
{
while (height[row][temp.back()] >= height[row][i]) temp.pop_back();
rig[i] = temp.back();
temp.push_back(i);
}
int res = 0;
for (int i = 1; i <= m; ++i) res = max(res, height[row][i]*(rig[i]-lef[i]-1));
return res;
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
cin >> arr[i][j];
if (arr[i][j] == 'F') height[i][j] = height[i-1][j] + 1;
// cout << height[i][j] << " ";
}
// cout << endl;
}
int res = 0;
for (int i = 1; i <= n; ++i)
{
res = max(res, func(i));
}
printf("%d", res*3);
return 0;
}