Description
一年一度的xuzhenyiOI2006在风景如画的大同中学举行。按照以往惯例，在激烈的比赛过程后，选手们会应邀去风景名胜区游览。今年当然也不例外。为了确定一条最佳的旅游路线，组委会请各位选手编一程序帮忙寻找。假设所有的风景点都集中在一个C列R行的矩阵中，矩阵的每一元素代表风景点或者障碍物。现在你要寻找一条满足下列条件的最佳旅游路线：
●这条路线上的每一点结点必须是风景点（即不能为障碍物）
●每个风景点最多游览一次
●这条路线必须是连续的相邻风景点的序列（若风景点A和B分别位于矩阵的位置（a1，a2）及（b1，b2），且|a1-b1|+|a2-b2|=1，则风景点A和B是相邻的）
●在满足上述条件下，游览的风景点尽可能多
假设任意的两个风景点都有且仅有一条路径（无回路）相连。显然，任意一个风景点都可以作为游览路线的起点或者终点。
输入格式 Input Format
第一行是两个整数C和R（3≤C，R≤1000），表示矩阵的列数和行数。
接下来有R行，每行有C个字符，每个字符都只能是‘#’或‘．’，‘#’表示障碍物，‘．’表示风景点。行手行末无多余空格。
输出格式 Output Format
只有一行，输出最佳路线的长度。
样例输入 Sample Input
3 3
###
#.#
###
样例输出 Sample Output
0
分析：
第一次从任意的一个可行点DFS找到一条最长的路径，再以最后找到的那个点再DFS找最长的一段路径即可。
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
char map[1010][1010];
bool vis[1010][1010];
int n,m,ans,xn,ym;
bool check(int x,int y)
{
if (x>0 && x<=n && y>0 && y<=m && map[x][y]=='.')
return true;
return false;
}
void dfs(int x,int y,int dep)
{
if (dep>ans)
{
ans=dep;
xn=x;ym=y;
//return ;
}
vis[x][y]=true;
int tx,ty;
for (int i=0;i<=3;i++)
{
tx=x+dx[i]; ty=y+dy[i];
if (!vis[tx][ty] && check(tx,ty)) dfs(tx,ty,dep+1);
}
vis[x][y]=false;
}
void get()
{
memset(vis,false,sizeof(vis));
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (map[i][j]=='.')
{
xn=i; ym=j;
vis[i][i]=true;
dfs(i,j,0);
return ;
}
}
void solve()
{
ans=0;
get();
memset(vis,false,sizeof(vis));
vis[xn][ym]=true;
ans=0;
dfs(xn,ym,0);
printf("%d\n",ans);
}
int main()
{
scanf("%d%d",&m,&n); getchar();
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++) scanf("%c",&map[i][j]);
getchar();
}
solve();
return 0;
}