路径规划对于自动驾驶来说是非常重要的一环,它决定了自动驾驶的车辆如何在道路上行驶。现在给出一个城市的地图,请规划出最快从起点到达终点的路线。
地图中的路都平行于X轴或Y轴,所有的路是双向通行的。路与路的交叉点有交通灯限制通行,所有的交通灯都是统一周期控制的。
交通灯共有三种不同的状态。第一种是只能右转,维持T1秒;第二种是可以直行左转和右转,维持T2秒;第三种是只能直行和右转,维持T3秒。
三种状态按顺序交替循环,即[0, T1), [T1 + T2 + T3, 2T1 + T2 + T3), [2T1 + 2T2 + 2T3, 3T1 + 2T2 + 2T3)时只能右转,[T1, T1 + T2), [2T1 + T2 + T3, 2T1 + 2T2 + T3), [3T1 + 2T2 + 2T3, 3T1 + 3T2 + 2T3)时可以直行左转和右转,[T1 + T2, T1 + T2 + T3), [2T1 + 2T2 + T3, 2T1 + 2T2 + 2T3), [3T1 + 3T2 + 2T3, 3T1 + 3T2 + 3T3)时可以直行和右转,如此类推。
路的中间和路口都无法掉头。假设车的速度为1单位长度/s,在起点处车可以自己选择启动的方向,给出起点和终点的坐标,问从起点开到终点最少需要的时间。