返回目录

题目描述

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

街道的街口（交叉点）有交通灯，灯的周期 T（=lightsrow）各不相同；

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

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

其中：

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

入口函数定义：

/**
 * @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，以空格分隔

输出描述

lightsrowStart 与 lightsrowEnd 两个街口之间的最短通行时间

示例：

解题思路

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

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

1. 优先队列：使用一个优先队列 pq（最小堆）来保持待访问节点的顺序，优先访问总成本（通行时间加等待时间）最小的节点。
2. 遍历：从起始点开始，按照Dijkstra算法的策略，每次从优先队列中取出一个节点，然后探索该节点能够直接到达的邻接节点（考虑上、下、左、右四个方向），更新这些邻接节点到起始点的最短时间，并将更新后的邻接节点加入优先队列。
3. 成本计算：在遍历过程中，对每个节点考虑直行或左转的情况（因为这两种情况需要等待红绿灯），如果是右转，则不需要等待红绿灯。每通过一个街口（非起点和终点），都需要加上通行时间 timePerRoad 和可能的等待时间。
4. 寻找最短路径：在所有可能的路径中，选择耗时最短的路径作为结果。因为每个街口都可以从四个方向到达，所以需要从到达终点的四个方向的最短时间中选择最小的一个。

Python算法源码

import heapq

# 定义四个方向的偏移量：上、右、下、左
offsets = [(-1, 0), (0, 1), (1, 0), (0, -1)]

# 计算从起点到终点的最短时间
def calcTime(lights, timePerRoad, rowStart, colStart, rowEnd, colEnd):
    n = len(lights)  # 行数
    m = len(lights[0])  # 列数

    # dist数组存储到每个点的最短时间，考虑四个方向
    dist = [[[float('inf')] * 4 for _ in range(m)] for _ in range(n)]

    # 优先队列，用于存储和选择下一个访问的节点
    pq = []
    for k in range(4):
        dist[rowStart][colStart][k] = 0
        heapq.heappush(pq, (0, rowStart, colStart, -1, -1, k))

    # 主循环，直到优先队列为空
    while pq:
        v, x, y, px, py, direction = heapq.heappop(pq)

        for k in range(4):
            newX = x + offsets[k][0]
            newY = y + offsets[k][1]

            # 检查新坐标是否有效
            if newX < 0 or newX >= n or newY < 0 or newY >= m:
                continue
            # 避免回到上一个节点
            if newX == px and newY == py:
                continue

            # 计算新的成本
            newCost = v + timePerRoad
            # 如果不是右转，则可能需要等红绿灯
            if (direction + 1) % 4 != k:  # 不是右转
                newCost += lights[x][y]

            # 更新最短路径和添加新节点到队列
            if newCost < dist[newX][newY][k]:
                dist[newX][newY][k] = newCost
                heapq.heappush(pq, (newCost, newX, newY, x, y, k))

    # 从四个方向中找到最短的时间
    ans = min(dist[rowEnd][colEnd])
    return ans

# 读取输入
n, m = map(int, input().split())
lights = []
for _ in range(n):
    lights.append(list(map(int, input().split())))
timePerRoad = int(input())
rowStart, colStart = map(int, input().split())
rowEnd, colEnd = map(int, input().split())

# 输出从起点到终点的最短时间
print(calcTime(lights, timePerRoad, rowStart, colStart, rowEnd, colEnd))

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

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

// 计算从起点到终点的最短时间
int calcTime(int **lights, int timePerRoad, int rowStart, int colStart, int rowEnd, int colEnd, int n, int m) {
    // 初始化距离数组
    int ***dist = (int***)malloc(n * sizeof(int**));
    for (int i = 0; i < n; i++) {
        dist[i] = (int**)malloc(m * sizeof(int*));
        for (int j = 0; j < m; j++) {
            dist[i][j] = (int*)malloc(4 * sizeof(int));
            for (int k = 0; k < 4; k++) {
                dist[i][j][k] = INT_MAX;
            }
        }
    }
  
    for (int k = 0; k < 4; ++k) {
        dist[rowStart][colStart][k] = 0;
    }

    // 使用优先队列
    typedef struct {
        int v, x, y, px, py, direction;
    } Node;

    Node *pq = (Node*)malloc(n * m * 4 * sizeof(Node));
    int pqSize = 0;

    for (int k = 0; k < 4; ++k) {
        pq[pqSize++] = (Node){0, rowStart, colStart, -1, -1, k};
    }

    while (pqSize > 0) {
        int minIndex = 0;
        for (int i = 1; i < pqSize; i++) {
            if (pq[i].v < pq[minIndex].v) {
                minIndex = i;
            }
        }

        Node current = pq[minIndex];
        pq[minIndex] = pq[--pqSize];

        for (int k = 0; k < 4; ++k) {
            int newX = current.x + offsets[k][0];
            int newY = current.y + offsets[k][1];

            if (newX < 0 || newX >= n || newY < 0 || newY >= m || (newX == current.px && newY == current.py)) continue;

            int newCost = current.v + timePerRoad;
            if ((current.direction + 1) % 4 != k) { // 如果不是右转
                newCost += lights[current.x][current.y];
            }

            if (newCost < dist[newX][newY][k]) {
                dist[newX][newY][k] = newCost;
                pq[pqSize++] = (Node){newCost, newX, newY, current.x, current.y, k};
            }
        }
    }

    // 从四个方向中找到最短的时间
    int ans = INT_MAX;
    for (int k = 0; k < 4; k++) {
        if (dist[rowEnd][colEnd][k] < ans) {
            ans = dist[rowEnd][colEnd][k];
        }
    }

    // 释放内存
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            free(dist[i][j]);
        }
        free(dist[i]);
    }
    free(dist);
    free(pq);

    return ans;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    // 读取输入
    int **lights = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        lights[i] = (int*)malloc(m * sizeof(int));
        for (int j = 0; j < m; j++) {
            scanf("%d", &lights[i][j]);
        }
    }
    int timePerRoad;
    scanf("%d", &timePerRoad);
    int rowStart, colStart;
    scanf("%d %d", &rowStart, &colStart);
    int rowEnd, colEnd;
    scanf("%d %d", &rowEnd, &colEnd);

    // 输出从起点到终点的最短时间
    printf("%d\n", calcTime(lights, timePerRoad, rowStart, colStart, rowEnd, colEnd, n, m));

    // 释放内存
    for (int i = 0; i < n; i++) {
        free(lights[i]);
    }
    free(lights);

    return 0;
}

Java算法源码

import java.util.*;

public class Main {
  
    // 定义四个方向的偏移量：上、右、下、左
    static int[][] offsets = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
  
    // 计算最短时间函数
    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;
      
        // 初始化距离数组，使用三维数组表示距离
        int[][][] dist = new int[n][m][4];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                Arrays.fill(dist[i][j], Integer.MAX_VALUE); // 将距离数组初始化为无穷大
            }
        }
      
        // 从起点出发，设置初始距离为0
        for (int k = 0; k < 4; k++) {
            dist[rowStart][colStart][k] = 0;
        }
      
        // 使用PriorityQueue实现的优先队列，按距离排序
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        for (int k = 0; k < 4; k++) {
            pq.offer(new int[]{0, rowStart, colStart, -1, -1, k}); // 初始状态入队
        }
      
        // 进行Dijkstra算法，计算最短路径
        while (!pq.isEmpty()) {
            int[] current = pq.poll(); // 取出当前距离最短的节点
            int v = current[0];
            int x = current[1];
            int y = current[2];
            int px = current[3];
            int py = current[4];
            int direction = current[5];
          
            // 遍历四个方向
            for (int k = 0; k < 4; k++) {
                int dx = offsets[k][0];
                int dy = offsets[k][1];
                int newX = x + dx;
                int newY = y + dy;
              
                // 检查是否超出边界或为回头路
                if (!(newX >= 0 && newX < n && newY >= 0 && newY < m) || (newX == px && newY == py)) {
                    continue; // 跳过不符合条件的路径
                }
              
                // 计算新的路径代价
                int newCost = v + timePerRoad;
                if ((direction + 1) % 4 != k) { // 如果不是右转
                    newCost += lights[x][y];
                }
              
                // 更新最短路径距离
                if (newCost < dist[newX][newY][k]) {
                    dist[newX][newY][k] = newCost;
                    pq.offer(new int[]{newCost, newX, newY, x, y, k}); // 将新路径加入队列
                }
            }
        }
      
        // 找到终点的最短路径
        int minTime = Integer.MAX_VALUE;
        for (int k = 0; k < 4; k++) {
            minTime = Math.min(minTime, dist[rowEnd][colEnd][k]);
        }
        return minTime; // 返回最短时间
    }
  
    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();
      
        // 计算并输出结果
        System.out.println(calcTime(lights, timePerRoad, rowStart, colStart, rowEnd, colEnd));
      
        scanner.close();
    }
}