习题7-1 消防车（Firetruck,ACM/ICPC World Finals 1991, UVa208)

本文主要是介绍习题7-1 消防车（Firetruck,ACM/ICPC World Finals 1991, UVa208)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-208
备注：回溯法
分类：DFS

代码如下：

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int kase, k, vis[25], pre[25], num;
vector<int>e[25];
void print_ans(int x) {if (pre[x])print_ans(pre[x]);printf("%d%c", x, x == k ? '\n' : ' ');
}
void dfs(int x) {if (x == k) { num++; print_ans(k); return; }vis[x] = 1;for (int i = 0; i < e[x].size(); i++) {if (vis[e[x][i]])continue;pre[e[x][i]] = x;dfs(e[x][i]);}vis[x] = 0;
}
int main(void) {while (~scanf("%d", &k)) {for (int i = 1; i <= 20; i++)e[i].clear();int a, b;while (~scanf("%d %d", &a, &b)) {if (a == 0 && b == 0)break;e[a].push_back(b);e[b].push_back(a);}bool ok = false;queue<int>Q;Q.push(1);vis[1] = 1;while (!Q.empty()) {int u = Q.front(); Q.pop();if (u == k) {ok = true; break;}for (int i = 0; i < e[u].size(); i++) {if (vis[e[u][i]])continue;vis[e[u][i]] = 1;Q.push(e[u][i]);}}memset(vis, 0, sizeof(vis));printf("CASE %d:\n", ++kase);if (!ok)printf("There are 0 routes from the firestation to streetcorner %d.\n", k);else {num = 0;for (int i = 1; i <= 20; i++)sort(e[i].begin(), e[i].end());dfs(1);printf("There are %d routes from the firestation to streetcorner %d.\n", num, k);}}return 0;
}

这篇关于习题7-1 消防车（Firetruck,ACM/ICPC World Finals 1991, UVa208)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---