消防车Firetruck(DFS+回溯)- UVA 208

题目描述

中心城市消防部门与运输部门合作,维护反映城市街道现状的城市地图。消防员需要能够选择从火警站到火警的路线。 中心城市分为不重叠的消防区。当报告发生火灾时,中央调度员通知火灾发生地区最近的火警站,并列出可能路线。您必须编写一个程序,中央调度员可以使用该程序来生成从地区火警站到火灾的路线。

输入

消防区都用小于 21 的正整数来标识,而且火场始终位于第一个消防区。输入文件包含多个测试用例,代表不同火灾。

• 测试用例的第一行由一个整数组成,该整数是距离火灾最近的火警站。

• 接下来的几行由成对的正整数组成,这些成对的正整数是开放街道相邻的消防区。(例如,如果对 4 7 在一行上,则消防区 4 和消防区 7 之间的街道是开放的。没有其他消防区在 4 和 7 之间。)

• 每个测试用例的最后一行由一对 0 组成。

输出

对于每个测试用例,您的输出必须通过编号来标识用例("CASE 1:","CASE 2:"等)。它必须列出每条路线,并按照字典序从小到大输出。它必须提供从火警站到火灾地点的总路线。 不同用例的输出必须分开显示。

样例输入

6 1 2 1 3 3 4 3 5 4 6 5 6 2 3 2 4 0 0 4 2 3 3 4 5 1 1 6 7 8 8 9 2 5 5 7 3 1 1 8 4 6 6 9 0 0

样例输出

CASE 1: 1 2 3 4 6 1 2 3 5 6 1 2 4 3 5 6 1 2 4 6 1 3 2 4 6 1 3 4 6 1 3 5 6 There are 7 routes from the firestation to streetcorner 6. CASE 2: 1 3 2 5 7 8 9 6 4 1 3 4 1 5 2 3 4 1 5 7 8 9 6 4 1 6 4 1 6 9 8 7 5 2 3 4 1 8 7 5 2 3 4 1 8 9 6 4 There are 8 routes from the firestation to streetcorner 4.

分析

  • 这道题主要就是要我们按照所给的地图,找到并按字典序输出火警到火灾地点的所有路径。
  • 这道题和以往不同的的是,并不是直接给出矩阵地图,而是通过给出点的连接情况来给出地图。这很容易让入门新手无从下手,但是如果你学过数据结构或者离散数学的话,你会知道我们可以把给出的图用矩阵表示。
    • 首先,我们要以比题目给的最大地点号(本题是21)稍大的值,来创建一个二维数组map[maxn][maxn]。
    • 然后,根据输入的连通情况,在矩阵上做标记。本题给的是个无向图,比如:输入了一个2 6,表示2和6之间连通,就在矩阵二行六列和六行二列的地方标记1(true)。
    • 题目给出样例一表示的矩阵为: 0 1 1 0 0 0 1 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0(注意:已经忽略0行0列)
  • 有了矩阵地图,这道题又可以像以前用搜索解决了。考虑到按字典序输出,我们用深度优先搜索比较恰当。
  • 这道题的样例输入比较麻烦,win7的控制台不能复制粘贴,如果我们要多次调试,输入数据会很烦。这里可以用一个,我刚刚学到的小技巧:
    • 首先,在.cpp所在的文件夹中创建一个test.txt文件,接着把要输入的数据黏贴到该.txt文件中。
    • 然后在main()函数中加入freopen("test.txt","r",stdin),即可实现文件输入。(该函数包含在cstdio头文件中)

代码如下

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=21+4;
int map[maxn][maxn]={0};//用来存储地图
int mark[maxn];//用来记录走过的点,以便输出
bool m[maxn];//用来记忆该点有没有被访问过
int n,ans1;//ans1记录总共有多少条路径
void dfs(int x,int ans)//x表示所在的地点,ans表示这是去到的第几个地点
{
    if(x==n)
    {
        ans1++;
        cout<<'1';
        for(int i=1;i<ans;i++)
            cout<<' '<<mark[i];
        cout<<endl;return ;
    }
    for(int i=2;i<maxn;i++)//从2开始逐个搜索,因为是从1出发,不能再回到1
        if(map[x][i]==1&&!m[i])//如果i点与x点连通,而且i点没被访问过
        {
            mark[ans]=i;m[i]=true;
            dfs(i,ans+1);
            m[i]=false;
        }
    return ;
}
int main()
{
    //freopen("text.txt","r",stdin);//文件输入
    int cnt=1;
    while(cin>>n)
    {
        memset(map,0,sizeof(map));//一轮下来,有些数据要被重置
        int x=1,y=1;
        ans1=0;//重置
        while(true)
        {
            cin>>x>>y;
            if(x==0||y==0)break;
            map[x][y]=map[y][x]=1;//构建矩阵地图
        }
        cout<<"CASE "<<cnt++<<":"<<endl;
        dfs(1,1);
        cout<<"There are "<<ans1<<" routes from the firestation to streetcorner "<<n<<"."<<endl;
    }
    return 0;
}

优化

  • 用回溯法预先找到能到达终点的路径,记录在bool fir[maxn]数组中。如果fir[i]=true,则说明该点能到达终点。 //似乎优化后跑得更慢了
void check(int x)
{
    fir[x]=true;
    for(int i=2;i<maxn;i++)
        if(map[x][i]&&!fir[i])
            check(i);
}
//还要每次用memset(fir,false,sizeof(fir));重置
//在dfs前调用check()函数
//dfs的条件改成if(map[x][i]==1&&!m[i]&&fir[i])

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-06-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据分析

[数据分析工具] Pandas 功能介绍(二)

我们需要看第一季度的数据是怎样的,就需要使用条件过滤

25170
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

SSE图像算法优化系列八:自然饱和度(Vibrance)算法的模拟实现及其SSE优化(附源码,可作为SSE图像入门,Vibrance算法也可用于简单的肤色调整)。

  Vibrance这个单词搜索翻译一般振动,抖动或者是响亮、活力,但是官方的词汇里还从来未出现过自然饱和度这个词,也不知道当时的Adobe中文翻译人员怎么会这...

69080
来自专栏小樱的经验随笔

鸽巢原理(抽屉原理)的详解

抽屉原理 百科名片 ? 桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放两个苹果。这一现象就是我们所说的“抽屉原理”...

51570
来自专栏冰霜之地

Google S2 是如何解决空间覆盖最优解问题的?

这篇不出意外就是 Google S2 整个系列的最终篇了。这篇里面会把 regionCoverer 算法都讲解清楚。至于 Google S2 库里面还有很多其他...

39230
来自专栏大数据挖掘DT机器学习

从互联网巨头数据挖掘类招聘笔试题目看我们还差多少

1 从阿里数据分析师笔试看职业要求 以下试题是来自阿里巴巴招募实习生的一次笔试题,从笔试题的几个要求我们一起来看看数据分析的职业要求。 一、异常值是指什么?请列...

39670
来自专栏PPV课数据科学社区

【学习】《R实战》读书笔记(第二章)

“读书会是一种在于拓展视野、宏观思维、知识交流、提升生活的活动。PPV课R语言读书会以“学习、分享、进步”为宗旨,通过成员协作完成R语言专业书籍的精读和分享,达...

36690
来自专栏阮一峰的网络日志

贝叶斯推断及其互联网应用(三):拼写检查

(这个系列的第一部分介绍了贝叶斯定理,第二部分介绍了如何过滤垃圾邮件,今天是第三部分。) 使用Google的时候,如果你拼错一个单词,它会提醒你正确的拼法。 比...

426120
来自专栏take time, save time

你所能用到的BMP格式介绍(一)

这些说明是我担任学校多媒体技术助教自己编写的实验说明,呕心沥血结合C++详细介绍BMP格式。  原理篇: 一、编码的意义。        让我们从一个简单的问题...

34370
来自专栏蜉蝣禅修之道

CMU算法求网络瓶颈链路

18760
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第14章 数据分析案例14.1 来自Bitly的USA.gov数据14.2 MovieLens 1M数据集14.3 1880-2010年间全美婴儿姓名14.4

本书正文的最后一章,我们来看一些真实世界的数据集。对于每个数据集,我们会用之前介绍的方法,从原始数据中提取有意义的内容。展示的方法适用于其它数据集,也包括你的。...

43150

扫码关注云+社区

领取腾讯云代金券