NC24034. [USACO 2016 Jan P]Fort Moo
描述
输入描述
Line 1 contains integers N and M.
The next N lines each contain M characters, forming a grid describing the site. A character of '.' represents normal grass, while 'X' represents a swampy spot.
输出描述
A single integer representing the maximum area that Bessie can cover with her fort.
示例1
输入:
5 6 ...... ..X..X X..X.. ...... ..X...
输出:
16
说明:
In the example, the placement of the optimal frame is indicated by 'f's below:C++11(clang++ 3.9) 解法, 执行用时: 28ms, 内存消耗: 720K, 提交时间: 2020-03-14 17:43:52
#include<stdio.h>
#include<iostream>
using namespace std;
const int N=205;
char a[N][N];
int n,m,i,j,k,x,y,ans,b[N][N];
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%s",a[i]+1);
for(j=1;j<=m;j++)
for(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];
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
{
x=0;
y=0;
for(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));
}
}
cout<<ans;
return 0;
}