欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PTA数据结构与算法 7-33 地下迷宫探索

程序员文章站 2022-06-08 08:11:12
...

如有不对,不吝赐教
进入正题:
地道战是在抗日战争时期,在华北平原上抗日军民利用地道打击日本侵略者的作战方式。地道网是房连房、街连街、村连村的地下工事,如下图所示。
PTA数据结构与算法 7-33 地下迷宫探索
我们在回顾前辈们艰苦卓绝的战争生活的同时,真心钦佩他们的聪明才智。在现在和平发展的年代,对多数人来说,探索地下通道或许只是一种娱乐或者益智的游戏。本实验案例以探索地下通道迷宫作为内容。

假设有一个地下通道迷宫,它的通道都是直的,而通道所有交叉点(包括通道的端点)上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点?

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 ;
}

测试结果:
PTA数据结构与算法 7-33 地下迷宫探索