AcWing 152. 城市游戏
原题链接
中等
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
const int N = 2000;
int h[N][N];
int n,m;
int main()
{
cin>>n >>m;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
char temp;
cin>> temp;
if(temp == 'F') h[i][j] = h[i-1][j] + 1;
else h[i][j] = 0;
}
}
//初始化矩阵后
long long res = 0;
for (int i = 1; i <= n; i ++ ) {
stack<int > stk;
stk.push(0);
for (int j = 1; j <= m+1; j ++ ) {
while(stk.size() && h[i][j] < h[i][stk.top()]) {
//边出栈,边计算前面出现的可能是最大面积的面积
int max_top = h[i][stk.top()];
//int max_top_pos = stk.top();
stk.pop();
int w = j - stk.top() -1;
res = max(res, 1ll*max_top * w);
}
stk.push(j);
}
}
cout << res*3 <<endl;
return 0;
}