学习了一下求树的最长链的方法
最简单的思路就是两次dfs
两次dfs分别有什么用呢？
第一次dfs，求出某个任意的点能到达的最远的点
第二次dfs，从所搜到的最远的点倒搜回去.
为什么需要两次呢？
其实很容易想通第一遍dfs的起始点或许并不是最长链的起点
从最远的点倒搜到的最长的链就是所求的解
（因为最长链一定经过这个最远的点啊...
这里注意题目表述：
假设任意的两个风景点都有且仅有一条路径（无回路）相连。显然，任意一个风景点都可以作为游览路线的起点或者终点。
这里就保证了题目中只有一个连通块，也就是从可走的任意点开始第一遍dfs都是可行的
mark一个小技巧的东西：
因为之前没有看清题目..就把所有的可以走的点都两遍dfs了..
T是肯定的...但是被D说dfs写得太丑...之前用vis[][] 记录是否搜过该点，需要每次dfs之前都memset一次，很浪费时间
学长表示可以每次dfs的时候+a，然后比较是否和之前递归进来的相等即可
然后附上这题代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
bool f[1001][1001];
int vis[1001][1001];
int temp=0,ans=0,maxn=0,maxx=0,markx,marky;
int dx,dy;
int n,m;
char s;
bool f1;
void dfs(int x,int y,int sum){
if(x<0 || x>n || y<0 || y>m || (vis[x][y]==vis[markx][marky] && !f1)){
if(sum>maxx){
maxx=sum;
dx=x;
dy=y;
}
return;
}
vis[x][y]++;
f1=0;
if(f[x-1][y]) dfs(x-1,y,sum+1);
if(f[x+1][y]) dfs(x+1,y,sum+1);
if(f[x][y-1]) dfs(x,y-1,sum+1);
if(f[x][y+1]) dfs(x,y+1,sum+1);
}
int main(){
//freopen("data.txt","r",stdin);
scanf("%d%d",&n,&m);
memset(f,false,sizeof(f));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>s;
if(s=='.') f[i][j]=1;
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
ans=0;
if(f[i][j]){
f1=1;
markx=i;marky=j;
dfs(i,j,0);
break;
}
}
f1=1;
markx=dx;marky=dy;
dfs(dx,dy,0);
printf("%d",maxx);
return 0;
}
编译成功
测试数据 #0: Accepted, time = 46 ms, mem = 5384 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 5364 KiB, score = 20
测试数据 #2: Accepted, time = 421 ms, mem = 5364 KiB, score = 20
测试数据 #3: Accepted, time = 187 ms, mem = 5412 KiB, score = 20
测试数据 #4: Accepted, time = 0 ms, mem = 5368 KiB, score = 20
Accepted, time = 654 ms, mem = 5412 KiB, score = 100
没有0ms过.....代码写得太挫了...