bzoj1661[Usaco2006 Nov]Big Square 巨大正方形*

bzoj1661[Usaco2006 Nov]Big Square 巨大正方形

题意：

n*n的图中有一些J点，一些B点和一些空白点，问在空白点添加一个J点所能得到的有4个J点组成最大正方形面积。n≤100。

题解：

枚举两个点，然后根据这两个点组成的边尝试在4个上下两个方向组成四边形。

代码：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 #define inc(i,j,k) for(int i=j;i<=k;i++)

 #define maxn 110

 using namespace std;

 char graph[maxn][maxn]; int n,ans;

 int main(){

     scanf("%d",&n); inc(i,,n)scanf("%s",graph[i]+);

     inc(i,,n)inc(j,,n)if(graph[i][j]=='J'){

         inc(k,i+,n){

             inc(l,,j){

                 int cnt=;

                 if(graph[k][l]=='B')continue; if(graph[k][l]=='J')cnt++;

                 int x=l-j,y=k-i;

                 if(k-x>n||l+y>n||graph[k-x][l+y]=='B')goto jump1; if(graph[k-x][l+y]=='J')cnt++;

                 if(i-x>n||j+y>n||graph[i-x][j+y]=='B')goto jump1; if(graph[i-x][j+y]=='J')cnt++;

                 if(cnt>=)ans=max(ans,(k-i)*(k-i)+(j-l)*(j-l));

                 jump1:;

                 if(k+x<||l-y<||graph[k+x][l-y]=='B')goto jump2; if(graph[k+x][l-y]=='J')cnt++;

                 if(i+x<||j-y<||graph[i+x][j-y]=='B')goto jump2; if(graph[i+x][j-y]=='J')cnt++;

                 if(cnt>=)ans=max(ans,(k-i)*(k-i)+(j-l)*(j-l));

                 jump2:;

             }

             inc(l,j+,n){

                 int cnt=;

                 if(graph[k][l]=='B')continue; if(graph[k][l]=='J')cnt++;

                 int x=l-j,y=k-i;

                 if(k-x<||l+y>n||graph[k-x][l+y]=='B')goto jump3; if(graph[k-x][l+y]=='J')cnt++;

                 if(i-x<||j+y>n||graph[i-x][j+y]=='B')goto jump3; if(graph[i-x][j+y]=='J')cnt++;

                 if(cnt>=)ans=max(ans,(k-i)*(k-i)+(j-l)*(j-l));

                 jump3:;

                 if(k+x>n||l-y<||graph[k+x][l-y]=='B')goto jump4; if(graph[k+x][l-y]=='J')cnt++;

                 if(i+x>n||j-y<||graph[i+x][j-y]=='B')goto jump4; if(graph[i+x][j-y]=='J')cnt++;

                 if(cnt>=)ans=max(ans,(k-i)*(k-i)+(j-l)*(j-l));

                 jump4:;

             }

         }

     }

     printf("%d",ans); return ;

 }

20161023