SDUT 3361 数据结构实验之图论四:迷宫探索

数据结构实验之图论四:迷宫探索

Time Limit: 1000MS Memory Limit: 65536KB

Submit Statistic Discuss

Problem Description

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

Input

连续T组数据输入,每组数据第一行给出三个正整数,分别表示地下迷宫的结点数N(1 < N <= 1000)、边数M(M <= 3000)和起始结点编号S,随后M行对应M条边,每行给出一对正整数,表示一条边相关联的两个顶点的编号。

Output

若可以点亮所有结点的灯,则输出从S开始并以S结束的序列,序列中相邻的顶点一定有边,否则只输出部分点亮的灯的结点序列,最后输出0,表示此迷宫不是连通图。
访问顶点时约定以编号小的结点优先的次序访问,点亮所有可以点亮的灯后,以原路返回的方式回到起点。

Example Input

1
6 8 1
1 2
2 3
3 4
4 5
5 6
6 4
3 6
1 5

Example Output

1 2 3 4 5 6 5 4 3 2 1

DQE:

本题题意一开始不太明确,参考了一下已AC的代码,意思是走的过程中遇到死路返回上一级,在走下一个可行节点,直到完成第一次深度优先搜索,判断计数变量和定点数是否相等,从而判定是否为连通图,非连通图和连通图输出序列一个套路,只是最后多个0。

需要注意的是多组数据,计数变量需要再每次开始深搜之前初始化为0,不可以用static定义在DFS函数里(这样只能初始化一次,笔者一开始犯的就是这个错误)。

 1 #include <iostream>
 2 #include <cstdio>
 3
 4 using namespace std;
 5
 6 #define MVN 1010    /*本地运行时改为100左右才可以,不然运行时错误,提交时改为1000+可AC*/
 7
 8 typedef struct AdjMatrix
 9 {
10     int w;
11     char *info;
12 }AM;
13
14 typedef struct MGraph
15 {
16     int vex[MVN];
17     AM arc[MVN][MVN];
18     int vexnum,arcnum;
19     int k;
20 }MG;
21
22 void creat(MG &G)
23 {
24     int i,j,k;
25     for(k=1;k<=G.vexnum;k++)
26     {
27         G.vex[k]=k;
28     }
29     for(k=1;k<=G.arcnum;k++)
30     {
31         scanf("%d %d",&i,&j);
32         G.arc[i][j].w=1;
33         G.arc[j][i].w=1;
34     }
35 }
36
37 int count=0;    //计数变量
38 int DFS(MG &G,bool *visited,int i)
39 {
40     count++;
41     visited[i]=true;
42     if(G.vex[i]==G.k)
43         printf("%d",G.k);
44     else
45         printf(" %d",G.vex[i]);
46     int k;
47     for(k=1;k<=G.vexnum;k++)
48     {
49         if(G.arc[i][k].w>0&&visited[k]==false)
50         {
51             DFS(G,visited,k);
52             printf(" %d",G.vex[i]);
53         }
54     }
55     return count;
56 }
57
58 int main()
59 {
60     int t;
61     scanf("%d",&t);
62     while(t--)
63     {
64         MG G={0};
65         scanf("%d %d %d",&G.vexnum,&G.arcnum,&G.k);
66         creat(G);
67         int k;
68         for(k=1;k<=G.vexnum;k++)
69         {
70             if(G.vex[k]==G.k)
71                 break;
72         }
73         bool visited[MVN]={false};
74         count=0;
75         if(DFS(G,visited,k)!=G.vexnum)
76             printf(" 0\n");
77         else
78             printf("\n");
79     }
80     return 0;
81 }
82
83 /***************************************************
84 User name: ***
85 Result: Accepted
86 Take time: 12ms
87 Take Memory: 1784KB
88 Submit time: 2016-11-08 21:57:57
89 ****************************************************/
时间: 11-06

SDUT 3361 数据结构实验之图论四:迷宫探索的相关文章

SDUT-3361_数据结构实验之图论四:迷宫探索

数据结构实验之图论四:迷宫探索 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 有一个地下迷宫,它的通道都是直的,而通道所有交叉点(包括通道的端点)上都有一盏灯和一个开关:请问如何从某个起点开始在迷宫中点亮所有的灯并回到起点? Input 连续T组数据输入,每组数据第一行给出三个正整数,分别表示地下迷宫的结点数N(1 < N <= 1000).边数M(M <= 3000)和起始结点编号S,随后M行对应M条边,

SDUT 3363 数据结构实验之图论七:驴友计划

数据结构实验之图论七:驴友计划 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description 做为一个资深驴友,小新有一张珍藏的自驾游线路图,图上详细的标注了全国各个城市之间的高速公路距离和公路收费情况,现在请你编写一个程序,找出一条出发地到目的地之间的最短路径,如果有多条路径最短,则输出过路费最少的一条路径. Input 连续T组数据输入,每组输入数据的第一行给出四个正整数N,M,s,d,其中N(2

SDUT 3343 数据结构实验之二叉树四:还原二叉树

数据结构实验之二叉树四:还原二叉树 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description 给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度. Input 输入数据有多组,每组数据第一行输入1个正整数N(1 <= N <= 50)为树中结点总数,随后2行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区分大小写)的字符串. Output 输出一个整数,即该二叉树的

SDUT 3362 数据结构实验之图论六:村村通公路

数据结构实验之图论六:村村通公路 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description 当前农村公路建设正如火如荼的展开,某乡镇政府决定实现村村通公路,工程师现有各个村落之间的原始道路统计数据表,表中列出了各村之间可以建设公路的若干条道路的成本,你的任务是根据给出的数据表,求使得每个村都有公路连通所需要的最低成本. Input 连续多组数据输入,每组数据包括村落数目N(N <= 1000)和可供

SDUT 3376 数据结构实验之查找四:二分查找

数据结构实验之查找四:二分查找 Time Limit: 20MS Memory Limit: 65536KB Submit Statistic Problem Description 在一个给定的无重复元素的递增序列里,查找与给定关键字相同的元素,若存在则输出找到的位置,不存在输出-1. Input 一组输入数据,输入数据第一行首先输入两个正整数n ( n < = 10^6 )和m ( m < = 10^4 ),n是数组中数据元素个数,随后连续输入n个正整数,输入的数据保证数列递增.随后m行输

SDUT 3364 数据结构实验之图论八:欧拉回路

数据结构实验之图论八:欧拉回路 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description 在哥尼斯堡的一个公园里,有七座桥将普雷格尔河中两个岛及岛与河岸连接起来. 能否走过这样的七座桥,并且每桥只走一次?瑞士数学家欧拉最终解决了这个问题并由此创立了拓扑学.欧拉通过对七桥问题的研究,不仅圆满地回答了哥尼斯堡七桥问题,并证明了更为广泛的有关一笔画的三条结论,人们通常称之为欧拉定理.对于一个连通图,通常把

SDUT 2498 数据结构实验之图论十一:AOE网上的关键路径

数据结构实验之图论十一:AOE网上的关键路径 Time Limit: 2000 ms Memory Limit: 65536 KiB Problem Description 一个无环的有向图称为无环图(Directed Acyclic Graph),简称DAG图.    AOE(Activity On Edge)网:顾名思义,用边表示活动的网,当然它也是DAG.与AOV不同,活动都表示在了边上,如下图所示:                                         如上所示

SDUT 3401 数据结构实验之排序四:寻找大富翁

数据结构实验之排序四:寻找大富翁 Time Limit: 200 ms Memory Limit: 512 KiB Problem Description 2015胡润全球财富榜调查显示,个人资产在1000万以上的高净值人群达到200万人,假设给出N个人的个人资产值,请你快速找出排前M位的大富翁. Input 首先输入两个正整数N( N ≤ 10^6)和M(M ≤ 10),其中N为总人数,M为需要找出的大富翁数目,接下来给出N个人的个人资产,以万元为单位,个人资产数字为正整数,数字间以空格分隔.

SDUT OJ 数据结构实验之栈四:括号匹配

#include<iostream> #include<stdio.h> using namespace std; int main() { char a[51],b[51]; int i,top; while(gets(a)!=NULL) { top=-1; for(i=0;a[i]!='\0';i++) { if(a[i]=='{'||a[i]=='['||a[i]=='(') { b[++top]=a[i]; } else if(a[i]=='}') { if(b[top]=