编程题实训-图

第1关：迷宫问题

任务描述

密密被困在一个迷宫里，迷宫有n个路口，编号为1-n。密密现在站在第一个路口，出口编号为m。先给出每个路口通向何处，问密密能否逃出迷宫。

编程要求

输入

多组数据，每组数据n+2行。第一行为一个正整数n代表路口的个数，之后n行，这n行中的第i行为第i个路口的向左路口、向前路口、向右路口。最后一行为一个正整数m代表迷宫的终点。当n=0时输入结束。

输出

每组数据输出一行，若密密能走出迷宫，输出“YES”，否则输出“NO”。

#include <iostream>
using namespace std;
int m,n;//m:出口编号  n:入口
int tag;//输出标记
int DFS(int k,int (*a)[3])
{//深度搜索第k层，k:当前路口
/**************begin************/
    if(k==m) //到达出口
    {
        tag=1;
        return 0;
    }
    for(int i=0;i<3;i++)//遍历向左路口、向前路口、向右路口
    {
        if(0!=a[k][i]&&tag!=1)//如果当前路口有通路，并且没有走过
        {
            DFS(a[k][i],a);//进入下一个路口 ，递归
        }
    }
    return 0;
    /**************end************/
}
int main()
{
	while(cin>>n)
	{
	if(n==0)break;
	int i,j;
	tag=0;
	int a[n+1][3];//迷宫
	for(i=1;i<=n;i++)
		for(j=0;j<3;j++)
			cin>> a[i][j];
	cin>>m;
	DFS(1,a);//从第一层开始搜索
	if(tag==1)
		cout<<"YES"<<endl;
	else if(tag==0)
		cout<<"NO"<<endl;
	}
	return 0;
}

第2关：基于Dijsktra算法的最短路径求解

任务描述

一张地图包括n个城市，假设城市间有m条路径（有向图），每条路径的长度已知。给定地图的一个起点城市和终点城市，利用Dijsktra算法求出起点到终点之间的最短路径。

编程要求

输入

多组数据，每组数据有m+3行。第一行为两个整数n和m，分别代表城市个数n和路径条数m。第二行有n个字符，代表每个城市的名字。第三行到第m+2行每行有两个字符a和b和一个整数d，代表从城市a到城市b有一条距离为d的路。最后一行为两个字符，代表待求最短路径的城市起点和终点。当n和m都等于0时，输入结束。

输出

每组数据输出两行。第一行为一个整数，为从起点到终点之间最短路的长度。第二行为一串字符串，代表该路径。每两个字符之间用空格隔开。

#include<iostream>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MaxInt 32767                        //最大值
#define MVNum 100                           //最大数量
using namespace std;
int D[MVNum];           //D[i]记录从源到终端的当前最短
int Path[MVNum];        //路径[i]记录是从源到终端上vi的当前最小序列号
typedef struct
{
    char vexs[MVNum];                   //点列表
    int arcs[MVNum][MVNum];               //连接到短端口阵列
    int vexnum;                           //数字总数
    int arcnum;                        //图中GL的总数
} AMGraph;
int LocateVex(AMGraph G,char u)
{//存储在“返回”表中的标签，无论是否返回
    int i;
    for(i=0;i<G.vexnum;i++)
        if(u==G.vexs[i])
            return i;
    return ERROR;
}
char OrigialVex(AMGraph G,int u)
{//以下文件u的元素作为表存储在返回表中？
    return G.vexs[u];
}
int CreateDN(AMGraph &G,int spot,int edge)
{//使用连接LPG阵列的方法创建定向屏蔽
    G.vexnum=spot;
    G.arcnum=edge;
    int i,j,k,w;
    char v1,v2;
    for(i=0;i<G.vexnum;++i)
        cin>>G.vexs[i];       //输入
    for(i=0;i<G.vexnum;++i) 
        for(j=0;j<G.vexnum;++j)
            G.arcs[i][j]=MaxInt;
    for(k=0;k<G.arcnum;++k)                     
    {
        cin>>v1>>v2>>w;       ///输入附着到第一个面板的标签
        i=LocateVex(G, v1);
        j=LocateVex(G, v2);  //确定v1和2之间的位置
        G.arcs[i][j]=w;    
    }//for
    return OK;
}
void ShortestPath_DIJ(AMGraph G, char V)
{//用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径
/**************begin************/
    int i,n,v,Min,w;
    int S[MVNum];           //S[i]记录从源链0到终点
    n=G.vexnum;                         //N列表中的项目数
    int v0=LocateVex(G,V);     
    for(v=0;v<n;++v)      
    {
        S[v]=false;                   //首为空
        D[v]=G.arcs[v0][v];             //分为不同终端的短期数据库的初始初始化更改为右上角的值
        if(D[v]<MaxInt)
            Path[v]=v0;                  //V0之间进行选择，并将v的第一个要求设置为V0
        else
            Path[v]=-1;                //如果v0和v0之间没有差异，则v0的第一个要求设置为1
    }//for
    S[v0]=true;                     //将0添加到S
    D[v0]=0;                            
    for(i=1;i<n;++i)       
    {
        Min=MaxInt;
        for(w=0;w<n;++w)
            if(!S[w]&&D[w]<Min)    
            {
                v=w;
                Min=D[w];
            }
        S[v]=true;                          //添加S
        for(w=0;w<n;++w)  
            if(!S[w]&&(D[v]+G.arcs[v][w]<D[w]))
            {
                D[w]=D[v]+G.arcs[v][w];     //更新D[w]
                Path[w]=v;                     //先前更改w的要求是v
            }//if
    }//for
    /**************end************/
}
void Find(AMGraph G,int v)
{//在路径编号组中查找程序编号
    if(Path[v]==-1)    
        return ;
    else
    {
        Find(G,Path[v]);   
        cout<<OrigialVex(G,Path[v])<<" ";   //输出点列表中标记有路径[v]的元素
    }
}
int main()
{
    char a,b;      
    int n,m;     
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        AMGraph G;
        CreateDN(G,n,m);          //创建定向屏蔽
        cin>>a;                 //输入
        ShortestPath_DIJ(G,a);  //如果G的接触点和它的静止点之间有一段短时间
        cin>>b;            //触点底座b
        int v=LocateVex(G,b);//返回地面表中的下一个标记，以验证测量值的数量
        cout<<D[v]<<endl;      //将它们之间的短距离输出到B
        Find(G,v);
        cout<<b<<endl;
    }
    return 0;
}

?