不可思议的事情发生了!交通部门制定的计划出了岔子。就在人们即将下班离开小镇隆恩雪平时,一场可怕的暴风雪导致镇上所有互联网中断。由于互联网中断,他们无法获取交通部门计划的最新信息,因此无法在不冒撞车风险的情况下开车回家。
现在你的任务是找到一种方法,让所有人都能安全回家,避免任何碰撞。隆恩雪平的道路网络由 座房屋和 条道路组成。每条道路直接连接两座房屋。如果你在某座房屋,可以通过道路前往与当前房屋相连的所有房屋。该网络还被构建成,可以通过一条或多条道路在任意两座房屋之间通行。
多亏了交通部门计划制定前的数据收集,你清楚每个人身在何处(他们都在工作,你知道他们的工作地点),以及他们想回哪个家。现在,每个人都坐在工作地点外的车里,挡住了其他车辆通过该房屋的道路。为了让所有人安全回家,你将使用一架无人机,它会飞来飞去,告诉人们“开车回家”。他们会沿着工作地点和家之间最短的路径开车回家,中途不停。一旦到家,他们会将车停入车库,不再阻碍任何道路。由于天气寒冷,无人机速度非常慢,你可以假设每个人都有足够的时间开车回家并停车,然后无人机才会到达下一个人那里。
如果一辆车开始回家,而路上有另一辆车挡道,由于路面湿滑,它们会发生碰撞。判断是否存在一个让所有汽车都能完全避免碰撞地开回家的顺序。如果存在,请找出它。