acdream 小晴天老师系列——晴天的后花园（暴力+剪枝）

　　　　　　小晴天老师系列——晴天的后花园

Time Limit: 10000/5000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

小晴天非常漂亮的后花园，打算以后退休之后在里面种种花，养养草，所以现在小晴天打算为他的后花园围上栅栏。

小晴天的后花园可以看成是一个m*n的矩形，但是其中有一些地方种了树，这些地方都不能安装栅栏，现在小晴天把后花园的平面图告诉你了，请你帮忙设计一个最大的矩形栅栏。

Input

单组数据，第一行包括两个整数m,n(1<=m,n<=500)，接下来m行，每行包括n个字符，仅由'x'和'.'组成（ASCII码分别是120与46）.

其中‘x’表示这个方格有树木，‘.’表示这个点可以建造栅栏

Output

若可以围成一个闭合栅栏，输出一个整数，表示栅栏能打到的最大周长

否则输出impossible

Sample Input

4 5

.....

.x.x.

.....

.....

2 2

.x

x.

2 5

.....

xxxx.

Sample Output

14

impossible

impossible

Hint

样例一可以绕着整个图一圈，周长为2*(4+3)=14

样例二与三因为有树木的存在，不能建造一个闭合的栅栏。

本题为单文件读写，样例包括三个文件

思路：暴力的话就是选两个点，穷举任意的矩形。但是这样可能会超时，加些必要的剪枝可以过。

　　穷举第一个点(x1,y1)，第二个点(x2,y2)。第一个点任意摆放，第2个点必须从x1+1，y1+1开始穷举，这样可以减少一些不必要的计算。首先要得到从第一个点开始，y1列可以到达哪列，即中间不能有任何树木，同理，行也是这样。然后第二个点的y2先穷举，遇到一个树就break，这样又减少了计算。这样子就保证了3个边都是无障碍的，另外一个边就得靠计算了，可以先预处理。

 /*

 * this code is made by xcw0754

 * Problem: 1705

 * Verdict: Accepted

 * Submission Date: 2015-07-15 23:53:13

 * Time: 28MS

 * Memory: 4664KB

 */

 #include <bits/stdc++.h>

 #define LL long long

 using namespace std;

 const int N=;

 int m, n;

 int g[N][N];

 int row[N][N];

 int col[N][N];

 LL ans;

 void secon(int r,int c)

 {

     int up_m=r;

     int up_n=c;

     while( up_m<=m && !g[up_m][c])  up_m++;

     while( up_n<=n && !g[r][up_n])  up_n++;

     for(int i=r+; i<up_m; i++)

     {

         for(int j=c+; j<up_n; j++)

         {

             if(g[i][j]) break;

             if( !(col[j][i]-col[j][r]) )

                 ans=max(ans, (LL)*(i-r)+*(j-c) );

         }

     }

 }

 int cal()   //穷举:从小开始，遇到点就结束

 {

     for(int i=; i<m; i++)

     {

         for(int j=; j<n; j++)

         {

             if(g[i][j]) continue;

             secon(i,j);

         }

     }

     return ans;

 }

 int main()

 {

     //freopen("e://input.txt","r",stdin);

     char c;

     scanf("%d%d",&m,&n);

     for(int i=; i<=m; i++)

     {

         getchar();

         for(int j=; j<=n; j++)

         {

             if(getchar()=='x')  g[i][j]=;

             row[i][j]=row[i][j-]+g[i][j];  //行先计算了

         }

     }

     for(int i=; i<=n; i++) //计算列的

         for(int j=; j<=m; j++)

             col[i][j]=col[i][j-]+g[j][i];

     for(int i=; i<n+; i++)    g[m+][i]=;

     for(int i=; i<m+; i++)    g[i][n+]=;

     if(!cal())  puts("impossible");

     else    printf("%lld\n",ans);

 }

AC代码

晴天