自动搬运

查看原文

来自洛谷，原作者为

	ROY1994 **

搬运于2025-08-24 21:59:57，当前版本为作者最后更新于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);
}