PTA数据结构与算法 7-33 地下迷宫探索
如有不对,不吝赐教
进入正题:
地道战是在抗日战争时期,在华北平原上抗日军民利用地道打击日本侵略者的作战方式。地道网是房连房、街连街、村连村的地下工事,如下图所示。
我们在回顾前辈们艰苦卓绝的战争生活的同时,真心钦佩他们的聪明才智。在现在和平发展的年代,对多数人来说,探索地下通道或许只是一种娱乐或者益智的游戏。本实验案例以探索地下通道迷宫作为内容。
假设有一个地下通道迷宫,它的通道都是直的,而通道所有交叉点(包括通道的端点)上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点?
输入格式:
输入第一行给出三个正整数,分别表示地下迷宫的节点数N(1<N≤1000,表示通道所有交叉点和端点)、边数M(≤3000,表示通道数)和探索起始节点编号S(节点从1到N编号)。随后的M行对应M条边(通道),每行给出一对正整数,分别是该条边直接连通的两个节点的编号。
输出格式:
若可以点亮所有节点的灯,则输出从S开始并以S结束的包含所有节点的序列,序列中相邻的节点一定有边(通道);否则虽然不能点亮所有节点的灯,但还是输出点亮部分灯的节点序列,最后输出0,此时表示迷宫不是连通图。
由于深度优先遍历的节点序列是不唯一的,为了使得输出具有唯一的结果,我们约定以节点小编号优先的次序访问(点灯)。在点亮所有可以点亮的灯后,以原路返回的方式回到起点。
输入样例1:
6 8 1
1 2
2 3
3 4
4 5
5 6
6 4
3 6
1 5
输出样例1:
1 2 3 4 5 6 5 4 3 2 1
输入样例2:
6 6 6
1 2
1 3
2 3
5 4
6 5
6 4
输出样例2:
6 4 5 4 6 0
这道题目其实就是DFS,题目说的非常清楚,我们只要注意下输出就可以了。
下面给出代码:
#include<stdio.h>
#include<malloc.h>
struct Vertax{
int index;
struct Vertax *next;
}; //邻接表存储图
int count=1; //记录已经访问过的节点的编号
int tag=0; //第一个节点不输出
void AddEdge(struct Vertax *v,int point);
void Dfs(struct Vertax *v[],int *vis,int i);
void Free(struct Vertax *v);
int main(void)
{
int N,M,S; //顶点数 边数 起始点编号(1到N编号)
fscanf(stdin,"%d %d %d",&N,&M,&S);
int i;
int vis[N+1]; //是否访问过该节点
int VIS[N+1]; //用于计数
int v1,v2;
struct Vertax *v[N+1];
for(i=0;i<=N;i++){
v[i]=(struct Vertax *)malloc(sizeof(struct Vertax));
v[i]->next=NULL;
v[i]->index=i;
vis[i]=0;
VIS[i]=0;
} //初始化邻接表
for(i=0;i<M;i++){
fscanf(stdin,"%d %d",&v1,&v2);
AddEdge(v[v1],v2);
AddEdge(v[v2],v1);
}
vis[S]=VIS[S]=1;
Dfs(v,vis,S);
if(count<N)
printf(" 0");
for(i=1;i<=N;i++)
if(v[i]->next)
Free(v[i]);
return 0;
}
void AddEdge(struct Vertax *v,int point)
{
struct Vertax *cur=v->next;
struct Vertax *newOne=(struct Vertax *)malloc(sizeof(struct Vertax));
newOne->index=point;
if(!cur){
newOne->next=NULL;
v->next=newOne;
return ;
}
if(cur->index>point){
newOne->next=cur;
v->next=newOne;
return ;
}
while(cur->next&&cur->index<point)
cur=cur->next;
newOne->next=cur->next;
cur->next=newOne;
return ;
}
void Dfs(struct Vertax *v[],int *vis,int i)
{ //第i个节点处理
vis[i]=1;
if(tag)
printf(" ");
else
tag=1; //只有第一个节点不要空格
printf("%d",v[i]->index); //输出自身节点
count++;
struct Vertax *cur=v[i]->next;
while(cur){
if(!vis[cur->index]){
Dfs(v,vis,cur->index);
printf(" %d",v[i]->index);
}
cur=cur->next;
}
return ;
}
void Free(struct Vertax *v)
{
struct Vertax *cur=v->next;
while(v->next){
v->next=cur->next;
free(cur);
cur=NULL;
cur=v->next;
}
return ;
}
测试结果:
上一篇: Yii框架中 find findAll 查找出制定的字段的方法对比
下一篇: 进出队列