UVA-208 Firetruck (回溯)

题目大意:给一张无向图,节点编号从1到n(n<=20),按字典序输出所有从1到n的路径。

题目分析:先判断从1是否能到n,然后再回溯。

注意:这道题有坑,按样例输出会PE。

代码如下:

# include<iostream>
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;

int mp[25][25],vis[25],ans;

bool ok(int s,int e)
{
    if(s==e)
        return true;
    vis[s]=1;
    for(int i=1;i<=20;++i)
        if(mp[s][i]&&!vis[i]&&ok(i,e))
            return true;
    return false;
}

void dfs(int s,int e,string p)
{
    if(s==e){
        ++ans;
        int l=p.size();
        for(int i=0;i<l;++i)
            printf("%d%c",p[i]-‘A‘+1,(i==l-1)?‘\n‘:‘ ‘);
    }
    for(int i=1;i<=20;++i){
        if(mp[s][i]&&!vis[i]){
            vis[i]=1;
            dfs(i,e,p+char(‘A‘+i-1));
            vis[i]=0;
        }
    }
}

int main()
{
    int n,a,b,cas=0;
    while(scanf("%d",&n)!=EOF)
    {
        memset(mp,0,sizeof(mp));
        while(scanf("%d%d",&a,&b)&&a+b)
            mp[a][b]=mp[b][a]=1;
        printf("CASE %d:\n",++cas);
        ans=0;
        memset(vis,0,sizeof(vis));
        if(ok(1,n)){
            memset(vis,0,sizeof(vis));
            vis[1]=1;
            dfs(1,n,"A");
        }
        printf("There are %d routes from the firestation to streetcorner %d.\n",ans,n);
    }
    return 0;
}

  

时间: 09-13

UVA-208 Firetruck (回溯)的相关文章

UVa 208 Firetruck【回溯】

题意:给出一个n个节点的无向图,以及某个节点k,按照字典序从小到大输出从节点1到节点k的所有路径 看的题解 http://blog.csdn.net/hcbbt/article/details/9755147 因为节点数很少(小于20),所以可以先用floyd处理一下,判断一点是否能够到达终点 然后就像紫书里面枚举排列那样的去挨个找出字典序从小到大的路径 题解里面说到的无回溯的走遍和终点相连的所有点,他写的代码是判断的d[en][i],判断终点到i点是否可达 写成d[i][en]也能过,因为是无

UVA - 208 Firetruck(消防车)(并查集+回溯)

题意:输入着火点n,求结点1到结点n的所有路径,按字典序输出,要求结点不能重复经过. 分析:用并查集事先判断结点1是否可以到达结点k,否则会超时.dfs即可. #pragma comment(linker, "/STACK:102400000, 102400000") #include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmat

(判连通+暴力)UVA - 208 Firetruck

原题链接: 比较麻烦,就不挂,可以上uva live找,也可以用virtual judge挂题. 题意: 输出从1到k的所有路径,不能重复经过 分析: 这题就是简单的深搜回溯,用一个数组记录路径,满足条件时输出.紫书上说需要先判断1到k是否联通,不然会超时.交了一发直接深搜,果然TLE.所以需要先判连通. 判连通的方法有(能想到的): 1.dfs和bfs,两者感觉差不多,但是我选择的bfs 2.floyd,n^3的复杂度,但更加粗暴直接,也更好写 3.待添加 感悟: 不预先判连通3000ms超时

Firetruck UVA - 208

DFS+并查集 如果只用DFS的话会超时,用并查集剪枝,和起点终点不联通的点就不用跑了 这题有好多人写了博客,但是我觉得我的代码写的比较通俗易懂所以就贴上来了,我觉得我写代码的目标就是让任何人都能看懂,越小白越好(其实是因为真小白吧-- #include<bits/stdc++.h> using namespace std; int E[30][30]; int diste; int mark[30]; int path[30]; int fin[30]; int ans; int root[

【UVa 208】Firetruck

The Center City ?re department collaborates with the transportation department to maintain mapsof the city which re?ects the current status of the city streets. On any given day, several streets areclosed for repairs or construction. Fire?ghters need

【UVa】208 Firetruck(dfs)

题目 题目 ? ? 分析 一开始不信lrj的话,没判联通,果然T了. 没必要全部跑一遍判,只需要判断一下有没有点与n联通,邻接表不太好判,但无向图可以转换成去判n与什么联通. 关于为什么要判,还是因为数据造的强,造了许多之前的节点情况巨多,然而所有节点都不和中点连接的情况...... ? ? 代码 #include <bits/stdc++.h> using namespace std; int n; vector<int> G[100]; vector<int> An

UVa 208 消防车(dfs+剪枝)

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=144 题意:给出一个n个结点的无向图以及某个结点k,按照字典序从小到大顺序输出从1到结点k的所有路径. 思路:如果直接矩阵深搜的话是会超时的,所以我们可以从终点出发,将与终点相连的连通块保存起来,这样dfs深搜时可以剪枝掉一些到达不了的点.只要解决了这个,dfs就是小问题. 这道题还有点坑的

UVa 208 救火车

题意:先给出离出火地点最近的路口,然后给出一些之间通畅的路口.要求给出所有从1号路口到火灾事故点的不含回路的简单路径. 思路:方法很容易想到,dfs即可.但是简单的dfs会超时,3s+. 之后看别人用了并查集,去了解了下并查集的思想.这里可以通过并查集提前判断一个路口是否和火灾路口想通,如果不通,则直接剪枝了.别看仅这一个优化,最后AC时间0.022,性能提升还是很多的.因为你早早地剪去一个结点,由它延伸下去的很多种情况都一并剪枝了的.也可以分析下直接dfs的复杂度,粗略地估算解答树结点的个数:

UVA 208 (DFS)

题意:找出1到T的所有路径: 坑点:一开始以为是到终点,读错了题意,没测试第二个样例,结果WA了4遍,坑大了: 1 #include <iostream> 2 #include <cmath> 3 #include <cstdio> 4 #include <cstring> 5 #include <cstdlib> 6 #include <sstream> 7 #include <algorithm> 8 #define

UVA 208 划水记录2

题目:题目描述中心城市消防部门与运输部门合作,维护反映城市街道现状的城市地图.消防员需要能够选择从火警站到火警的路线. 中心城市分为不重叠的消防区.当报告发生火灾时,中央调度员通知火灾发生地区最近的火警站,并列出可能路线.您必须编写一个程序,中央调度员可以使用该程序来生成从地区火警站到火灾的路线. 输入消防区都用小于 21 的正整数来标识,而且火场始终位于第一个消防区.输入文件包含多个测试用例,代表不同火灾. ? 测试用例的第一行由一个整数组成,该整数是距离火灾最近的火警站. ? 接下来的几行由