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

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 ;

}

秒客网