城市游戏
题目 城市游戏
思路分析
就是 最大矩形 先把rf变成01就行了
怎么处理成这样
读入时 是F就读1
也可以同时处理成第二状态
是1 就变成上面的那个+1
可以把第零行置0 这样第一行也可以按这个方式处理
省的特判
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N][N];
int l[N],r[N],s[N];
int n,m;
int work(int h[]){
h[0]=h[m+1]=-1;//处理边界情况 最左最右有个高度不可能更小的柱子
int top=0;
s[0]=0;
//求左边最近的小于 左边开始遍历 栈内应为单增 所以出现往下趋势 出栈
for(int i=1;i<=m;i++){
while(h[i]<=h[s[top]])
top--;
l[i]=s[top];
s[++top]=i;
}
top=0;
s[0]=m+1;
//求右边最近的小于 右边开始遍历 栈内应为单增 所以出现往下趋势 出栈
for(int i=m;i>=1;i--){
while(h[i]<=h[s[top]])
top--;
r[i]=s[top];
s[++top]=i;
}
int res=0;
for(int i=1;i<=m;i++)
res=max(res,h[i]*(r[i]-l[i]-1));
return res;
}
int main()
{
cin>>n>>m;
//从1开始 便于处理第一行的1（也等于上一行的0加上1）
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char c;
cin>>c;
if (c=='F')
a[i][j]=a[i-1][j]+1;
}
}
// for(int i=0;i<=n;i++){
// for(int j=0;j<=m;j++){
// cout<<a[i][j]<<" ";
// }
// cout<<endl;
// }
int res=0;
for(int i=1;i<=n;i++){
res=max(res,work(a[i]));
}
cout<<res*3;
return 0;
}
💬 评论