首页 > 代码库 > 环游大同80天 cruisedt
环游大同80天 cruisedt
【题目描述】：
一年一度的IOI在风景如画的大同中学举行。按照以往惯例，在激烈的比赛过程后，选手们会应邀去风景名胜区游览。今年当然也不例外。为了确定一条最佳的旅游路线，组委会请各位选手编一程序帮忙寻找。假设所有的风景点都集中在一个C列R行的矩阵中，矩阵的每一元素代表风景点或者障碍物。现在你要寻找一条满足下列条件的最佳旅游路线：
●这条路线上的每一点结点必须是风景点（即不能为障碍物）
●每个风景点最多游览一次
●这条路线必须是连续的相邻风景点的序列（若风景点A和B分别位于矩阵的位置（a1，a2）及（b1，b2），且|a1-b1|+|a2-b2|=1，则风景点A和B是相邻的）
●在满足上述条件下，游览的风景点尽可能多
假设任意的两个风景点都有且仅有一条路径相连。显然，任意一个风景点都可以作为游览路线的起点或者终点。
【输入描述】：
第一行是两个整数C和R（3≤C，R≤1000），表示矩阵的列数和行数。
接下来有R行，每行有C个字符，每个字符都只能是‘#’或‘．’，‘#’表示障碍物，‘．’表示风景点。行手行末无多余空格。
【输出描述】：
只有一行，输出最佳路线的长度。
【样例输入】 | 【样例输出】 |
3 3 ### #.# ### | 0 |
【数据范围及描述】：
题解说是 树上最长链（并不懂是什么东西）
两遍正反dfs就好了：
任取一个点，求它所能到达的最远点，在从最远点dfs再找最远点，就是答案！！！
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn=1005; 8 const int dx[]={1,-1,0,0}; 9 const int dy[]={0,0,1,-1};10 char g[maxn][maxn];11 int R,C;12 bool vis[maxn][maxn];13 bool been[maxn][maxn];14 int X,Y,mx;15 16 void dfs(int x,int y,int c)17 {18 been[x][y]=true;19 bool flag=false;20 for(int i=0;i<4;i++)21 {22 int xx=x+dx[i];23 int yy=y+dy[i];24 if(xx>=1&&xx<=R&&yy>=1&&yy<=C&&!vis[xx][yy]&&g[xx][yy]==‘.‘)25 {26 vis[xx][yy]=true;27 flag=true;28 dfs(xx,yy,c+1);29 vis[xx][yy]=false;30 }31 }32 if(!flag&&mx<c) 33 {34 mx=c;35 X=x,Y=y;36 }37 return;38 }39 40 int main()41 {42 scanf("%d %d",&C,&R);43 for(int i=1;i<=R;i++)44 gets(g[i]+1);45 memset(vis,false,sizeof(vis));46 memset(been,false,sizeof(been));47 int ans=-1;48 for(int i=1;i<=R;i++)49 for(int j=1;j<=C;j++)50 {51 if(!been[i][j]&&g[i][j]==‘.‘) 52 {53 mx=-1;vis[i][j]=true;54 dfs(i,j,0);vis[i][j]=false;55 mx=-1;vis[X][Y]=true;56 dfs(X,Y,0);vis[X][Y]=false;57 ans=max(ans,mx);58 }59 }60 printf("%d",ans);61 return 0;62 }
环游大同80天 cruisedt
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。