由疫情出行延申到有关地图的计算机算法


疫情下,“我”的出行(一)



现在距离春节还有一个多月。

有句古话叫做:每逢佳节倍思亲。我现在确实也有种恨不得立马回家的冲动。

但是比较让人揪心的是,最近又有了 2 次疫情反弹。浙江绍兴,很不巧就在笔者老家——浙江嘉兴的边上。然后我有几个比较要好的大学同学就在西安工作,现在西安也是因为疫情被封城了。

从大的角度来说,疫情对人和社会都有非常大的坏处,希望能尽早结束疫情;从我个人的角度来说,这下不得不担忧起我的春节计划。本想在回家(浙江)之前去见一见朋友,这下感觉两地都进出非常困难。也是非常希望疫情能够尽快结束。

当然目前来看趋势还是稳中带好。落笔时,此时浙江的确诊新增只有一例,基本已经阻断了疫情的传播;西安方面,快速开展多个核酸检测点,并且控制出行,防止再次传播。我认为国家关于解决这方面问题的经验还是非常充分,也对本次疫情的处理充满信心。

那么,我们本次就以疫情下的出行,从计算机算法的角度,去做一些非常简单展现。当然设计到的算法语法内容会比较多,可能同时也比较简陋。希望读者多多包涵。

(本文讨论的疫情相关问题只为引申出算法知识,不含任何额外拓展含义。)


 AUT  UMN 


图的存储

首先我们要明确一个问题。地图是怎么表示的。一般来说,地图的表示方式多种多样,简单提炼一下,便是一个个的地点(点)和一条条的路径(边)。

所以我们可以用 n 个点和 m 条边来简单的描述一张图。具体的,点包含什么信息(有多少人,什么建筑等等),边包含多少信息(道路宽度、长度、是否单行,速度上限等)还是需要根据具体问题具体分析。

今天就只看最简单的模型,假设因为疫情原因出现封区,封城,我想知道现在 2 个地点是否可以互相到达。

点——仅表示地点。

边——仅表现一条双向路径,连接 2 个点,表示这 2 个点互相可达。

在这种情况下,我们就可以用一种最简单的方式来经行图的存储——二维数组。

由疫情出行延申到有关地图的计算机算法


 AUT  UMN 


判断连通

现在我们是明确知道了任意 2 个地点之间是否有边相连。那么进一步,怎么判断任意 2 个地点(x 和y)是否连通呢?

例如:1 连通 2;2 连通 3。虽然 1 和 3 没有直接边可以到达,但是 1 可以先到达 2,再到达 3。

方法其实比较多,有并查集维护连通性、直接搜索等等。本次也用较为简单和好理解的深搜/递归/洪水填充(floodfill)算法来解决。

我们利用数组给出发点 x 染色为1。

由疫情出行延申到有关地图的计算机算法


然后以 x 为触发点开始做递归深搜。

由疫情出行延申到有关地图的计算机算法


那么最终,只需要看目标点 y 和 x 的颜色是否相同即可。

由疫情出行延申到有关地图的计算机算法


这样就可以快速判断两点是否可达到。甚至于如果提前对整张图染色,那么之后每次询问都可以利用 color 数组在 O(1) 的时间内直接返回结果。具体实现方式留给读者自己思考,本文不多赘述。


零基础程序语言入门班

零基础程序语言入门班详情介绍


学员要求

对编程有兴趣,零基础的孩子。


上课时间

每周日下午2-5点


上课地点

福田区百花新天地3楼


师资介绍

何老师,计算机专业硕士保送生,现役ACM-ICPC队员,今年获得ICPC银川站金牌,CCPC银牌,EC铜牌以及邀请赛金牌。何老师不仅参赛成绩斐然,在教学上也有丰富经验,曾担任2019年CSP-S提高组集训班老师,以及数据结构专题班老师,教学细致耐心。


课表详情:

由疫情出行延申到有关地图的计算机算法



详情可扫描二维码联系郑老师咨询了解

由疫情出行延申到有关地图的计算机算法

毕莘教育咨询(深圳)有限公司围绕信息学竞赛普及组、提高组、省赛、国赛进行培训,同时提供与信息学相关的高校自主招生政策咨询。教研团队由国内顶校师资构成,深圳本地教学团队由来自清华、北大等顶尖名校的硕士、博士研究生及NOI、ACM- ICPC退役选手组成。自成立已开展多次培训,服务学生数百人次。

原创文章,作者:深圳信息学_中小学编程_编程培训_信息学竞赛_毕莘教育咨询(深圳)有限公司,如若转载,请注明出处:深圳信息学_中小学编程_编程培训_信息学竞赛_毕莘教育咨询(深圳)有限公司

联系我们

教务老师:余老师
联系电话(微信同号):14774755240
在线咨询:点击QQ在线咨询

QR code