题目描述

假定街道是棋盘型的，每格距离相等，车辆通过每格街道需要时间均为 timePerRoad；

街道的街口（交叉点）有交通灯，灯的周期 T（=lights[row][col]）各不相同；

车辆可直行、左转和右转，其中直行和左转需要等相应 T 时间的交通灯才可通行，右转无需等待。

现给出 n * m 个街口的交通灯周期，以及起止街口的坐标，计算车辆经过两个街口的最短时间。

其中：

1. 起点和终点的交通灯不计入时间，且可以在任意方向经过街口
2. 不可超出 n * m 个街口，不可跳跃，但边线也是道路（即：lights[0][0] -> lights[0][1] 是有效路径）

入口函数定义：

/**
 * @param lights：n*m个街口每个交通灯的周期，值范围[0, 120]，n和m的范围为[1,9]
 * @param timePreRoad：相邻两个街口之间街道的通行时间，范围为[0,600]
 * @param rowStart：起点的行号
 * @param colStart：起点的列号
 * @param rowEnd：终点的行号
 * @param colEnd：终点的列号
 * @return lights[rowStart][colStart] 与 lights[rowEnd][colEnd] 两个街口之间的最短通行时间
 */
int calcTime(int[][] lights, int timePreRoad, int rowStart, int colStart, int rowEnd, int colEnd)

输入描述

第一行输入 n 和 m，以空格分隔

之后 n 行输入 lights矩阵，矩阵每行m个整数，以空格分隔

之后一行输入 timePerRoad

之后一行输入 rowStart colStart，以空格分隔

最后一行输入 rowEnd colEnd，以空格分隔

输出描述

lights[rowStart][colStart] 与 lights[rowEnd][colEnd] 两个街口之间的最短通行时间

用例

输入

3 3
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) 走了4格路，2个右转，1个左转，共耗时 60+0+60+5+60+0+60=245

解题思路

此题目的核心解法涉及到使用图的搜索算法，具体是利用Dijkstra算法来找出从起点到终点的最短路径时间。Dijkstra算法用于在加权图中找到某一节点到其他节点的最短路径。此题中加权图的节点是街口，权重是通过街道的时间加上等待红绿灯的时间。

解题思路和算法详解如下：

1. 优先队列：使用一个优先队列 pq（最小堆）来保持待访问节点的顺序，优先访问总成本（通行时间加等待时间）最小的节点。

2. 遍历：从起始点开始，按照Dijkstra算法的策略，每次从优先队列中取出一个节点，然后探索该节点能够直接到达的邻接节点（考虑上、下、左、右四个方向），更新这些邻接节点到起始点的最短时间，并将更新后的邻接节点加入优先队列。

3. 成本计算：在遍历过程中，对每个节点考虑直行或左转的情况（因为这两种情况需要等待红绿灯），如果是右转，则不需要等待红绿灯。每通过一个街口（非起点和终点），都需要加上通行时间 timePerRoad 和可能的等待时间。

4. 寻找最短路径：在所有可能的路径中，选择耗时最短的路径作为结果。因为每个街口都可以从四个方向到达，所以需要从到达终点的四个方向的最短时间中选择最小的一个。

Java

import java.util.PriorityQueue;
import java.util.Scanner;

class Solution {
    // 定义四个方向的偏移量：上、右、下、左
    static int[][] offsets = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    // 计算从起点到终点的最短时间
    static int calcTime(int[][] lights, int timePerRoad, int rowStart, int colStart, int rowEnd, int colEnd) {
        int n = lights.length; // 行数
        int m = lights[0].length; // 列数

        // dist数组存储到每个点的最短时间，考虑四个方向
        int[][][] dist = new int[n][m][4];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < 4;