题解 P3135 【[USACO16JAN]堡哞Fort Moo】

大菜鸡fks · 2018-05-13 11:01:17 · 题解

这题主要就是枚举。 固定左右两边，O（n）枚举中间部分

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=205;
int n,m,b[N][N];
char a[N][N];
inline void init(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%s",a[i]+1);
    }
    for (int j=1;j<=m;j++){
        for (int i=1;i<=n;i++){
            if (a[i][j]=='X') b[i][j]=b[i-1][j]+1;
                else b[i][j]=b[i-1][j];
        }
    }
}
int ans;
inline void solve(){
    for (int i=1;i<=n;i++){
        for (int j=i;j<=n;j++){
            int x=0,y=0;
            for (int k=1;k<=m;k++){
                if (b[j][k]-b[i-1][k]==0){
                    x=max(x,k);
                    y=x;
                    while (x<m&&a[i][x+1]=='.'&&a[j][x+1]=='.'){
                        x++;
                        if (b[j][x]-b[i-1][x]==0) y=x;
                    }
                    ans=max(ans,(j-i+1)*(y-k+1));
                }
            }
        }
    }
    printf("%d\n",ans);
}
int main(){
    init();
    solve();
    return 0;
}