AcWing 152. 城市游戏
原题链接
中等
作者:
溪染
,
2020-11-05 09:25:46
,
所有人可见
,
阅读 601
变量解释
h[i][j] 点(i,j)对应的悬线的长度
l[i][j] 点(i,j)到左边的第一个障碍的长度(若没有,则为边界)
r[i][j] 点(i,j)到右边的第一个障碍长度(若没有,则为边界)
L[i][j] 点(i,j)对应的悬线能移动到的最左边的长度
R[i][j] 点(i,j)对应的悬线能移动到的最右边的长度
#include<bits/stdc++.h>
using namespace std;
char t;
int n,m,ans;
int h[1005][1005],a[1005][1005];
int l[1005][1005],r[1005][1005];
int L[1005][1005],R[1005][1005];
int main()
{
memset(L,10,sizeof(L));
memset(R,10,sizeof(R));
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>t;
a[i][j]= t=='F';
}
for(int i=1;i<=n;i++){
int pos=0;
for(int j=1;j<=m;j++)
if(a[i][j]) l[i][j]=++pos;
else l[i][j]=pos=0;
pos=0;
for(int j=m;j>=1;j--)
if(a[i][j]) r[i][j]=++pos;
else r[i][j]=pos=0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]){
h[i][j]=h[i-1][j]+1;
L[i][j]=min(L[i-1][j],l[i][j]);
R[i][j]=min(R[i-1][j],r[i][j]);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=max(ans,h[i][j]*(L[i][j]+R[i][j]-1));
cout<<ans*3<<"\n";
return 0;
}