路口最短时间问题 - 华为OD统一考试

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

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

假定街道是棋盘型的，每格距离相等，车辆通过每格街道需要时间均为 timePerRoad；街道的街口（交叉点）有交通灯，灯的周期T(=lights[row][col])各不相同；

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

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

其中：

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

入口函数定义:

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

此题核心编程模式，实现对应方法即可。

示例1

输入：
[[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

题解

数据量不大，此题采用回溯法求解。

从四个方向到达起点，然后按照题目要求进行一步步的探索，直到所有的方案都探索完成，此时输出到达目标位置最短的时间。

Java

/*** @author code5bug*/
class Solution {private int[][] lights;private int timePerRoad;private int rowEnd, colEnd;private boolean[][][] vis;private int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};  // 上、右、下、左private int result;/*** lights : n*m 个街口每个交通灯的周期，值范围[0,120]，n和m的范围为[1,9]* timePerRoad : 相邻两个街口之间街道的通过时间,范围为[0,600]* rowStart : 起点的行号* colStart : 起点的列号* rowEnd : 终点的行号* colEnd : 终点的列号* return : lights[rowStart][colStart] 与 lights[rowEnd][colEnd] 两个街口之间的最短通行时间*/public int calcTime(int[][] lights, int timePerRoad, int rowStart, int colStart, int rowEnd, int colEnd) {int n = lights.length, m = lights[0].length;this.lights = lights;this.timePerRoad = timePerRoad;this.rowEnd = rowEnd;this.colEnd = colEnd;this.result = Integer.MAX_VALUE;this.vis = new boolean[n][m][4];for (int d = 0; d < 4; d++) { // 从四个方向到达起点， 寻找到达目标位置路口最短的时间dfs(rowStart, colStart, d, 0);}return result != Integer.MAX_VALUE ? result : -1;}private boolean valid(int row, int col) {return 0 <= row && row < vis.length && 0 <= col && col < vis[0].length;}private void dfs(int row, int col, int direction, int time) {if (vis[row][col][direction] || time >= result) { // 剪枝： 已经遍历过 或 时间不会更短return;}// 到达终点if (row == rowEnd && col == colEnd) {result = Math.min(result, time);return;}vis[row][col][direction] = true;for (int d = -1; d <= 1; d++) {int newDir = (direction + d + 4) % 4;int dr = directions[newDir][0], dc = directions[newDir][1];int newRow = row + dc, newCol = col + dr;if (!valid(newRow, newCol)) continue;if (d == -1 || d == 0) { // 左转或直行dfs(newRow, newCol, newDir, time + timePerRoad + lights[row][col]);} else {  // 右转，不需要路口等待时间dfs(newRow, newCol, newDir, time + timePerRoad);}}vis[row][col][direction] = false;}
}

Python

from math import infclass Solution:# 返回通过指定路口之间的最短时间# @param lights int整型二维数组 n*m 个街口每个交通灯的周期，值范围[0,120]，n和m的范围为[1,9]# @param timePerRoad int整型 相邻两个街口之间街道的通过时间,范围为[0,600]# @param rowStart int整型 起点的行号# @param colStart int整型 起点的列号# @param rowEnd int整型 终点的行号# @param colEnd int整型 终点的列号# @return int整型def calcTime(self, lights, timePerRoad, rowStart, colStart, rowEnd, colEnd):n, m = len(lights), len(lights[0])directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]  # 上、右、下、左vis = [[[False] * 4] * m for _ in range(n)]def valid(row, col):return 0 <= row < n and 0 <= col < mdef dfs(row, col, direction, time):nonlocal resultif vis[row][col][direction] or time >= result:return# 到达终点if row == rowEnd and col == colEnd:result = min(result, time)returnvis[row][col][direction] = Truefor d in range(-1, 2, 1):new_dir = (direction + d + 4) % 4dr, dc = directions[new_dir]new_row, new_col = row + dc, col + drif not valid(new_row, new_col):continueif d == -1 or d == 0:  # 左转或直行dfs(new_row, new_col, new_dir, time +timePerRoad + lights[row][col])else:  # 右转dfs(new_row, new_col, new_dir, time + timePerRoad)vis[row][col][direction] = Falseresult = inffor d in range(4):dfs(rowStart, colStart, d, 0)return result if result != inf else -1

C++

class Solution {
private:vector<vector<int>> lights;int timePerRoad;int rowEnd, colEnd;vector<vector<vector<bool>>> vis;vector<vector<int>> directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上、右、下、左int result;public:int calcTime(vector<vector<int>>& lights, int timePerRoad, int rowStart, int colStart, int rowEnd, int colEnd) {int n = lights.size(), m = lights[0].size();this->lights = lights;this->timePerRoad = timePerRoad;this->rowEnd = rowEnd;this->colEnd = colEnd;this->result = INT_MAX;this->vis = vector<vector<vector<bool>>>(n, vector<vector<bool>>(m, vector<bool>(4, false)));for (int d = 0; d < 4; d++) {dfs(rowStart, colStart, d, 0);}return result != INT_MAX ? result : -1;}private:bool valid(int row, int col) {return 0 <= row && row < vis.size() && 0 <= col && col < vis[0].size();}void dfs(int row, int col, int direction, int time) {if (vis[row][col][direction] || time >= result) {return;}// 到达终点if (row == rowEnd && col == colEnd) {result = min(result, time);return;}vis[row][col][direction] = true;for (int d = -1; d <= 1; d++) {int newDir = (direction + d + 4) % 4;int dr = directions[newDir][0], dc = directions[newDir][1];int newRow = row + dc, newCol = col + dr;if (!valid(newRow, newCol)) {continue;}if (d == -1 || d == 0) { // 左转或直行dfs(newRow, newCol, newDir, time + timePerRoad + lights[row][col]);} else { // 右转，不需要路口等待时间dfs(newRow, newCol, newDir, time + timePerRoad);}}vis[row][col][direction] = false;}
};