呵呵算法题

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

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

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

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

其中：

起点和终点的交通灯不计入时间，且可以在任意方向经过街口
不可超出 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

import java.util.*;

public class StreetNavigation {

    public static int calcTime(int[][] lights, int timePerRoad, int rowStart, int colStart, int rowEnd, int colEnd) {
        int n = lights.length;
        int m = lights[0].length;

        // Directions: right, down, left, up (clockwise)
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        // Priority queue to store the current minimum distance nodes
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, rowStart, colStart, -1});  // {current time, row, col, previous direction}

        // Distance array to keep track of the minimum time to reach each street corner
        int[][] dist = new int[n][m];
        for (int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dist[rowStart][colStart] = 0;

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int currTime = curr[0];
            int r = curr[1];
            int c = curr[2];
            int prevDir = curr[3];

            // If we've reached the end, return the current time
            if (r == rowEnd && c == colEnd) {
                return currTime;
            }

            for (int d = 0; d < 4; d++) {
                int nr = r + directions[d][0];
                int nc = c + directions[d][1];

                if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                    int waitTime = 0;
                    if (prevDir != -1) {
                        if (d == (prevDir + 2) % 4) {
                            // Going straight (opposite direction)
                            waitTime = lights[r][c] - (currTime % lights[r][c]);
                            if (waitTime == lights[r][c]) waitTime = 0;
                        } else if ((d + 2) % 4 == prevDir) {
                            // Turning left
                            waitTime = lights[r][c] - (currTime % lights[r][c]);
                            if (waitTime == lights[r][c]) waitTime = 0;
                        }
                        // Turning right has no wait time
                    }
                    
                    int newTime = currTime + timePerRoad + waitTime;

                    if (newTime < dist[nr][nc]) {
                        dist[nr][nc] = newTime;
                        pq.offer(new int[]{newTime, nr, nc, d});
                    }
                }
            }
        }

        return dist[rowEnd][colEnd];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] lights = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                lights[i][j] = scanner.nextInt();
            }
        }
        int timePerRoad = scanner.nextInt();
        int rowStart = scanner.nextInt();
        int colStart = scanner.nextInt();
        int rowEnd = scanner.nextInt();
        int colEnd = scanner.nextInt();
        scanner.close();

        System.out.println(calcTime(lights, timePerRoad, rowStart, colStart, rowEnd, colEnd));
    }
}