bzoj4506: [Usaco2016 Jan]Fort Moo(暴力)

时间:2021-07-23 20:36:30

4506: [Usaco2016 Jan]Fort Moo

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 145  Solved: 104
[Submit][Status][Discuss]

Description

Bessie正在和她的朋友Elsie建一座堡垒。像任何好的堡垒一样,这需要从一个坚固的框架开始。Bessie想要在一
个矩形上建造堡垒,并在矩形周围围上1x1的框架。Bessie已经选择了一个建造堡垒的地方 —— 一块长宽分别为
为NM的土地(1<= N,M<= 200)。不幸的是,该地区有一些沼泽,不能用于支持框架。 请帮助贝西确定她可以用于
建造堡垒的最大矩形区域,避免框架搭建在任何一块沼泽上。题目大意:有一个NM的矩形包含字符‘.’和‘X’,
找出最大的边缘不包含‘X’的子矩形并输出它的面积。
 
 

Input

第一行包含整数N和M。接下来的N行每行包含M个字符,形成网格描述区域,‘.’表示正常的草地,‘X’表示沼泽
 
 

Output

一个整数,表示Bessie可以用她的堡垒覆盖的最大面积。

Sample Input

5 6
......
..X..X
X..X..
......
..X...

Sample Output

16
In the example, the placement of the optimal frame is indicated by 'f's below:
.ffff.
.fX.fX
Xf.Xf.
.ffff.
..X...
 
/*
预处理每个点能往上下左右扩展的距离
n^2枚举每个点n^2暴力扩展
复杂度n^4
emmm 加点优化就过了
*/
#include<bits/stdc++.h> #define N 201 using namespace std;
int n,m,ans,cnt;
int a[N][N];
int ex_up[N][N],ex_down[N][N],ex_L[N][N],ex_R[N][N];
char ch; int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) for(int j=;j<=m;j++)
{
cin>>ch;
a[i][j]=(ch=='.'?:);
}
for(int i=;i<=n;i++) for(int j=;j<=m;j++)
{
cnt=;
while(j+cnt<=m && !a[i][j+cnt]) cnt++;
if(cnt) ex_R[i][j]=cnt-;
cnt=;
while(j-cnt>= && !a[i][j-cnt]) cnt++;
if(cnt) ex_L[i][j]=cnt-;
cnt=;
while(i-cnt>= && !a[i-cnt][j]) cnt++;
if(cnt) ex_up[i][j]=cnt-;
cnt=;
while(i+cnt<=n && !a[i+cnt][j]) cnt++;
if(cnt) ex_down[i][j]=cnt-;
}
ans=;
for(int i=;i<=n;i++) for(int j=;j<=m;j++)
{
if(!ex_R[i][j]) continue;
if((ex_R[i][j]+)*(ex_down[i][j]+)<=ans) continue;
for(int x=j;x<=j+ex_R[i][j];x++)
{
if(!ex_down[i][x]) continue;
for(int y=i;y<=i+ex_down[i][j];y++)
{
if(i+ex_down[i][x]>n || j+ex_R[y][j]>m) continue;
if(i+ex_down[i][x]>=y && j+ex_R[y][j]>=x) ans=max(ans,(x-j+)*(y-i+));
}
}
}
printf("%d\n",ans);
return ;
}