uva 208

本文主要是介绍uva 208，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：从起点到终点的路，有几条路径，单纯的深搜或广搜是不行的，因为这不再是简单图，可能存在环，所以我们的方法是，先从终点开始广度搜索，把可以到达的点标记，然后在从起点进行深搜

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 22 ;int maps[MAXN][MAXN];
int visited[MAXN];
int path[MAXN],truck[MAXN];
int pointer;
int goal,routes;void init(int cur) // dfs预处理，从goal开始寻找可达路
{int i ;truck[cur] = 1 ;for (i = 1; i < MAXN; i++)if (maps[cur][i] && !truck[i])init(i);
}void dfs(int n)
{int i;if (n == goal){routes++;printf("1");for (i = 1; i < pointer; i++)printf(" %d",path[i]);printf("\n");}else {for ( i = 1 ; i < MAXN ; i++)if (maps[n][i] && !visited[i] && truck[i]){path[pointer++] = i;visited[i] = 1;dfs(i);visited[i] = 0;pointer--;   // notice }}
}int main()
{int a,b,Case=1;while (scanf("%d",&goal) != EOF){routes = 0 ;pointer = 0 ;memset(truck,0,sizeof(truck));memset(maps,0,sizeof(maps));memset(visited,0,sizeof(visited));while (1){scanf("%d%d",&a,&b);if (!a && !b)break;else maps[a][b] = maps[b][a] = 1;}printf("CASE %d:\n",Case++);path[pointer++] = 1;visited[1] = 1 ;init(goal);dfs(1);printf("There are %d routes from the firestation to streetcorner %d.\n",routes,goal);}return 0 ;
}

这篇关于uva 208的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---