题解 P4417 【[COCI2006-2007#2] STOL】

ROY1994 · 2018-09-20 15:52:20 · 题解

枚举区间 l ~ r

再计算最多有多少行在 l ~ r 上没有 X

可以每行用前缀和维护 X 的数量

时间复杂度 O(n^2)

#include <bits/stdc++.h>
using namespace std;
char a[405][405];
int sum[405][405];
int r,s,ans=-10000;
int main()
{
    scanf("%d%d",&r,&s);
    for(int i=1;i<=r;i++)
        scanf("%s",a[i]+1);
    for(int i=1;i<=r;i++)
        for(int j=1;j<=s;j++)
            if(a[i][j]=='X') sum[i][j]=sum[i][j-1]+1;
            else sum[i][j]=sum[i][j-1]; 
    for(int ll=1;ll<=s;ll++)
        for(int rr=ll;rr<=s;rr++)
        {
            int maxn=0,len=0;
            for(int i=1;i<=r;i++)
            {
                if(sum[i][rr]-sum[i][ll-1]==0) len++,maxn=max(maxn,len);
                else len=0;
            }
            if(maxn==0) continue;
            ans=max(ans,maxn*2+(rr-ll+1)*2-1);
        }
    printf("%d",ans);
}