OD C卷 - 路口最短时间问题

2024-08-22 01:52
文章标签 问题 od 短时间 路口

本文主要是介绍OD C卷 - 路口最短时间问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

路口最短时间问题 (200)

  • 街道是棋盘型的,(十字路口)每格距离相等,车辆通过每格的街道时间均为time_per_road;
  • 十字路口有交通灯,此处车辆可直行、左转、右转,直行和左转需要等待相应T时间;右转无需等待;
  • 现给出n*m个街口的交通灯等待时间,及街口的起止坐标,计算车辆从起始到终止的最短时间;
  • 终点路口的等待时间不计入;
    输入描述:
    每个十字路口的等待时间(二维数组),街道通过时间,起始点,终止点
    如:
    [[1, 2, 3], [4, 5, 6], [7, 8, 9]],60,0,0,2,2
    输出描述:
    从起始点到终点的最短时间
    245
    说明,以上行走路径为(0,0)->(0,1)->(1,1)->(1,2)->(2,2) 2个右转,一个左转,共耗时60+0+60+5+60+0+60=245

思路:

  • 为确定直行、右转、左转的方向,所以需要分情况讨论进入起始十字路口的方向;

    • 分别以上、右、下、左四个方向进入起始点,并设定进入的时间为0,入队,然后开始BFS;
    • 每种方向情况下,计算出可以走的直行、右转、左转方向,再开始行走到下一个位置,若时间更少,则放入队列;
      在这里插入图片描述
  • 期间时间的累加,非右转时,红灯等待时间 + 街道通行时间;右转只有街道通行时间;

  • 使用result 二维数组表示到达每个十字路口的最小时间(包括四个方向)

  • 最后取终点位置四个方向的最小值;


import queue# 上、右、下、左
directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]def calcTime(lights, time_per_road, row_start, col_start, row_end, col_end):# 二维数组的行、列数col = col_end + 1row = row_end + 1# result 表示 以哪种方式转弯,通过街道后进入该十字路口# [#   [1, 2, 3],#   [4, 5, 6],#   [7, 8, 9]# ]  每个数字表示该十字路口的等待时间,即 lights# result 则把对应的数字替换为[inf, inf, inf, inf]# 表示分别以四种方式转弯,通过街道到达该位置的最短时间result = [[[float('inf') for i in range(4)] for j in range(col)] for k in range(row)]# 队列pq = queue.Queue()# 进入起始十字路口 可以有四种方式,针对具体每种方式,才可以确定从该路口通过时# 的直行、右转、左转for i in range(4):# 进入十字路口的 每种方式入队 i -> 0, 1, 2, 3 对应directions的索引pq.put([0, [row_start, col_start, i, 0]]) # 以第i种方式转弯,然后通过街道后,进入到起始点位置,时间初始化为0# 起始点,每种方式的进入,时间都设置为0result[row_start][col_start][i] = 0# 从初始点开始走while True:if pq.qsize() <= 0:breakelse:point_t = pq.get() # 出队print("point", point_t)point = point_t[1] # [0, 0, 0, 0]# 当前方式转弯 进入该点的时间,若比 result 中已有的对应时间大,则跳过if point[3] > result[point[0]][point[1]][point[2]]:continue# 当前以point[2]转弯方式,通过街道进入该point十字路口,通过该路口时# 直行、右转、左转方向计算for i in range(4):# 确定方向的索引cur_direct = (point[2] + i) % 4# if not (directions[i][0] == 1 and directions[i][1] == 0): # 方向 (1, 0) 不能走if not (cur_direct == (point[2] + 2) % 4): # 其他方向都是可以走# 新位置点new_x = point[0] + directions[cur_direct][0]new_y = point[1] + directions[cur_direct][1]# 判断新位置点是否有效if 0 <= new_x < row and 0 <= new_y < col:# 通过中间街道 耗时new_time = point[3] + time_per_road# cur_direct 不是右转时,还要累加红灯等待时间# if not (directions[i][0] == 0 and directions[i][1] == 1):if not (cur_direct == (point[2] + 1) % 4):# 加街口的等待时间new_time += lights[point[0]][point[1]] # 通过的上一个十字路口 红灯等待# 以cur_direct 转弯/直行,并通过街道到达新位置的时间为new_time# 以更小的时间更新resultif new_time < result[new_x][new_y][cur_direct]:result[new_x][new_y][cur_direct] = new_time # 取更小的时间pq.put([new_time, [new_x, new_y, cur_direct, new_time]])print(result)return min(result[row_end][col_end])lights = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
time_per_road = 60
row_start = 0
col_start = 0
row_end = 2
col_end = 2min_time = calcTime(lights, time_per_road, row_start, col_start, row_end, col_end)
print(min_time)

 

这篇关于OD C卷 - 路口最短时间问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1094906

相关文章

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

Java程序运行时出现乱码问题的排查与解决方法

《Java程序运行时出现乱码问题的排查与解决方法》本文主要介绍了Java程序运行时出现乱码问题的排查与解决方法,包括检查Java源文件编码、检查编译时的编码设置、检查运行时的编码设置、检查命令提示符的... 目录一、检查 Java 源文件编码二、检查编译时的编码设置三、检查运行时的编码设置四、检查命令提示符

Jackson库进行JSON 序列化时遇到了无限递归(Infinite Recursion)的问题及解决方案

《Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursion)的问题及解决方案》使用Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursi... 目录解决方案‌1. 使用 @jsonIgnore 忽略一个方向的引用2. 使用 @JsonManagedR