此题深入浅出上的代码大致为:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1010;
int n,m;
char a[N][N];
int h[N][N],l[N][N],r[N][N],ans;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
h[i][j]=1;
r[i][j]=l[i][j]=j;
}
for(int j=2;j<=m;j++){
if(a[i][j]=='F'&&a[i][j-1]=='F')l[i][j]=l[i][j-1];
}
for(int j=m-1;j>=1;j--){
if(a[i][j]=='F'&&a[i][j+1]=='F')r[i][j]=r[i][j+1];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i!=1&&a[i][j]=='F'){
if(a[i-1][j]=='F'){
h[i][j]=h[i-1][j]+1;
l[i][j]=max(l[i][j],l[i-1][j]);
r[i][j]=min(r[i][j],r[i-1][j]);
}
ans=max(ans,(r[i][j]-l[i][j]+1)*h[i][j]);
}
}
}
cout<<ans*3;
return 0;
}
写法有细微差别。
用的悬线法,可以 AC,但是代码里为了防止越界对i=1的时候加了特判,而更新又是写在特判里的
所以无法处理有些 n=1 的数据:
1 2
F F
代码给出 0
应该这么写:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1010;
int n,m;
char a[N][N];
int h[N][N],l[N][N],r[N][N],ans;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
h[i][j]=1;
r[i][j]=l[i][j]=j;
}
for(int j=2;j<=m;j++){
if(a[i][j]=='F'&&a[i][j-1]=='F')l[i][j]=l[i][j-1];
}
for(int j=m-1;j>=1;j--){
if(a[i][j]=='F'&&a[i][j+1]=='F')r[i][j]=r[i][j+1];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i!=1&&a[i][j]=='F'){
if(a[i-1][j]=='F'){
h[i][j]=h[i-1][j]+1;
l[i][j]=max(l[i][j],l[i-1][j]);
r[i][j]=min(r[i][j],r[i-1][j]);
}
}
if(a[i][j]=='F')ans=max(ans,(r[i][j]-l[i][j]+1)*h[i][j]);
}
}
cout<<ans*3;
return 0;
}
如果是我自己眼瞎请告知一下。