https://vjudge.net/contest/189603#problem/E
这一道题,思想较难,编码虽简单但坑多。
如果用暴力,需要n*n*m*m,要超时,所以我们要用优化算法,逐行逐列地寻找最大的面积,用n*m,具体解释看注释
#include<cstdio>
#include<algorithm>
using namespace std;
int a[1005][1005];
char x;
int up[1005][1005],lef[1005][1005],righ[1005][1005];
int t,m,n;
int ans;
int lo,ro;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
x=getchar();
while(x!='F'&&x!='R')x=getchar();
if(x=='R')a[i][j]=0;
else a[i][j]=1;
}
}
ans=0;
for(int i=1;i<=n;i++){
lo=0,ro=m+1;//lo为左边最近的障碍,ro为右边最近的障碍
for(int j=1;j<=m;j++){
if(a[i][j]==0){
up[i][j]=lef[i][j]=righ[i][j]=0;//如果自己是个障碍
lo=j;//暂时左边最近的障碍是自己
}
else {
up[i][j]=up[i-1][j]+1;//因为当前的不是障碍,所以高度是上面的那个+1
lef[i][j]=(i==1)?lo+1:max(lef[i-1][j],lo+1);//如果上面没有东西,
//则左边的结束点设置为 最近障碍处的右边一个
}
}
for(int j=m;j>=1;j--){
if(a[i][j]==0){
righ[i][j]=m;
ro=j;// 暂时右边最近的障碍是自己
}
else {
righ[i][j]=(i==1)?ro-1:min(righ[i-1][j],ro-1);//这个长方形的右边界是
//算右边界最多到哪儿 ,既不能到最近障碍,也不能超过上面那个的宽
ans=max(ans,up[i][j]*(righ[i][j]-lef[i][j]+1));//计算面积
}
}
}
printf("%d
",ans*3);
}
return 0;
}