4506: [Usaco2016 Jan]Fort Moo
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 145 Solved: 104[][][]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#define N 201using 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=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>ch; a[i][j]=(ch=='.'?0:1); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cnt=0; while(j+cnt<=m && !a[i][j+cnt]) cnt++; if(cnt) ex_R[i][j]=cnt-1; cnt=0; while(j-cnt>=1 && !a[i][j-cnt]) cnt++; if(cnt) ex_L[i][j]=cnt-1; cnt=0; while(i-cnt>=1 && !a[i-cnt][j]) cnt++; if(cnt) ex_up[i][j]=cnt-1; cnt=0; while(i+cnt<=n && !a[i+cnt][j]) cnt++; if(cnt) ex_down[i][j]=cnt-1; } ans=1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(!ex_R[i][j]) continue; if((ex_R[i][j]+1)*(ex_down[i][j]+1)<=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+1)*(y-i+1)); } } } printf("%d\n",ans); return 0;}