hdu 5024 Wang Xifeng's Little Plot 2014 ACM/ICPC Asia Regional Guangzhou Online dfs

題目連結:hdu 5024

        給定一張圖,求出圖上存在的最長折線段的長度。（可以不拐）

        對每一個點深搜,找出各個方向上能拓展的長度。枚舉每個點作為拐點時的情況，找出所有長度的最大值

/******************************************************
 * File Name:   1003.cpp
 * Author:      kojimai
 * Creater Time:2014年09月20日 星期六 12時25分46秒
 ******************************************************/

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
#define FFF 105
int n;
struct node
{
	int h1,h2;
	int l1,l2;
	int x1,x2;
	int y1,y2;
}p[FFF][FFF];
char s[FFF][FFF];
int solve(int x,int y)
{
	int i,j;
	if(y==0||s[x][y-1]=='#')//左右方向的拓展
	{
		//cout<<"fuck1"<<endl;
		p[x][y].h1=1;
		for(i=1;;i++)
		{
			if(s[x][y+i]=='#'||i+y==n)
			{
				p[x][y].h2=i;
				break;
			}
			p[x][y+i].h1=i+1;
		}
		for(j=i-1;j+y>y;j--)
		{
			p[x][y+j].h2=p[x][y].h2-p[x][y+j].h1+1;
		}
	}
	if(x==0||s[x-1][y]=='#')
	{
		p[x][y].l1=1;
		for(i=1;;i++)
		{
			if(i+x==n||s[x+i][y]=='#')
			{
				p[x][y].l2=i;
				break;
			}
			p[x+i][y].l1=i+1;
		}
		for(j=i-1;j>0;j--)
			p[x+j][y].l2=p[x][y].l2-p[x+j][y].l1+1;
	}
		//cout<<"fuck2"<<endl;
	if(x==0||y==0||s[x-1][y-1]=='#')
	{
		//cout<<"fuck3"<<endl;
		p[x][y].x1=1;
		for(i=1;;i++)
		{
			if(x+i==n||y+i==n||s[x+i][y+i]=='#')
			{
				p[x][y].x2=i;
				break;
			}
			p[x+i][y+i].x1=i+1;
		}
		for(j=i-1;j>0;j--)
		{
			p[x+j][y+j].x2=p[x][y].x2-p[x+j][y+j].x1+1;
		}
	}
	if(x==0||y==n-1||s[x-1][y+1]=='#')
	{
		//cout<<"fuck4"<<endl;
		p[x][y].y1=1;
		for(i=1;;i++)
		{
			if(x+i==n||y-i<0||s[x+i][y-i]=='#')
			{
				p[x][y].y2=i;
				break;
			}
			p[x+i][y-i].y1=i+1;
		}
		for(j=i-1;j>0;j--)
		{
			p[x+j][y-j].y2=p[x][y].y2-p[x+j][y-j].y1+1;
		}
	}
//	if(x==0&&y==2)
//	{
//		cout<<p[x][y].l1<<' '<<p[x][y].l2<<' '<<p[x][y].h1<<' '<<p[x][y].h2<<' '<<p[x][y].x1<<' '<<p[x][y].x2<<' '<<p[x][y].y1<<' '<<p[x][y].y2<<endl;
//	}
	int ret1,ret2;
	ret1=max(p[x][y].l1,p[x][y].l2)+max(p[x][y].h1,p[x][y].h2)-1;
	ret2=max(p[x][y].x1,p[x][y].x2)+max(p[x][y].y1,p[x][y].y2)-1;
	return max(ret1,ret2);
}
int main()
{
	while(scanf("%d",&n),n)
	{
		for(int i=0;i<n;i++)
		{
			scanf("%s",s[i]);
			//<cout<<i<<' '<<s[i]<<endl;
		}
		int ans=0;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
		//		cout<<i<<' '<<j<<endl;
				if(s[i][j]=='.')
					ans=max(ans,solve(i,j));
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}