学步园

本来是打算对每个可行点做BFS,每个点都有两个方向的分量，然后扩展点只扩展与之前垂直的方向。不过看了别人的Blog发现直接枚举拐点更容易，复杂度N*N*16*N

本机调试了好久，结果是因为有个地方敲错了。。果真以后结果不对要先仔细看看代码。。。。

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
using namespace std;

const int maxn=110;
int N;
int mp[maxn][maxn];
int ans;
int dx[]={0,-1,0,1,-1,-1,1,1};
int dy[]={-1,0,1,0,-1,1,1,-1};
int vertical[9]={1,2,3,0,5,6,7,4};//预处理垂直的方向
void bruteforce()
{
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            if(mp[i][j]==1)
            {
              //  cout<<i<<" "<<j<<endl;
                for(int d=0;d<8;d++)
                {
                    int d2=vertical[d];
                    int len=1;
                    int x=i;
                    int y=j;
                    bool dd=0;
                    while(x+dx[d]>=0&&x+dx[d]<N&&y+dy[d]>=0&&y+dy[d]<N&&mp[x+dx[d]][y+dy[d]]==1)
                    {
                        x=x+dx[d];
                        y=y+dy[d];
                        len++;
                        dd=1;
                  //      if(i==0&&j==0) cout<<d<<" d "<<x<<" "<<y<<" "<<len<<endl;
                    }
                 //   cout<<endl;
                    x=i;
                    y=j;
                    bool dd2=1;
                    while(x+dx[d2]>=0&&x+dx[d2]<N&&y+dy[d2]>=0&&y+dy[d2]<N&&mp[x+dx[d2]][y+dy[d2]]==1)
                    {
                        dd2=0;
                        x=x+dx[d2];
                        y=y+dy[d2];
                        len++;
                   //     if(i==0&&j==0) cout<<d<<" d2 "<<x<<" "<<y<<" "<<len<<endl;
                    }
                    ans=max(ans,len);
                   // cout<<dx[d]<<" "<<dy[d]<<endl;
                    //cout<<i<<" "<<j<<" "<<len<<endl;
                    //cout<<i<<" "<<j<<endl;

                }

            }
        }
    }

}
int main()
{
    freopen("input.txt","r",stdin);
  //  freopen("data.txt","r",stdin);
  //  freopen("out1.txt","w",stdout);

  while(true)
  {
      scanf("%d",&N);
      memset(mp,0,sizeof(mp));
      ans=0;
      if(N==0) break;
      else
      {
          char s;
          for(int i=0;i<N;i++)
          {
              for(int j=0;j<N;j++)
              {
                //scanf("%c",&s);
                cin>>s;
                if(s=='#')
                {
                    mp[i][j]=0;
                }
                else if(s=='.')
                {
                    mp[i][j]=1;
                }
              }
          }
          bruteforce();
          printf("%d\n",ans);
      }
  }
    return 0;
}