C++）网站首页 技术交流

【2024年华为OD机试】(C卷,200分)- 路口最短时间问题（JavaScript&Java & Python&C/C++）

妄北y 2025-08-31 12:01:05

简介【2024年华为OD机试】(C卷,200分)- 路口最短时间问题（JavaScript&Java & Python&C/C++）

在这里插入图片描述

一、问题描述

题目描述
假定街道是棋盘型的，每格距离相等，车辆通过每格街道需要时间均为 timePerRoad。街道的街口（交叉点）有交通灯，灯的周期 T（T = lights[row][col]）各不相同。车辆可直行、左转和右转，其中直行和左转需要等相应 T 时间的交通灯才可通行，右转无需等待。

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

其中：

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

入口函数定义：
javajava
/

@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。

用例图示如下：

(0,0) 是起点，(2,2) 是终点。

上面红色路径是起点到终点的最短时间路径，各线段花费时间如下：

(0,0) → (0,1)：由于是初始，因此不需要等待，仅花费 timePerRoad = 60 单位时间。
(0,1) → (1,1)：发生了右拐，因此不需要等待，仅花费 timePerRoad = 60 单位时间。
(1,1) → (1,2)：发生了左拐，因此需要等待，花费时间为 timePerRoad + lights[1][1] = 60 + 5 单位时间。
(1,2) → (2,2)：发生了右拐，因此不需要等待，仅花费 timePerRoad = 60 单位时间。

最终总耗时为：60 + 60 + (60 + 5) + 60 = 245。

题目解析
本题看上去是单源最短路径问题，但实际操作起来并不适用某些常规算法，以下以 Dijistra 算法模拟过程来说明：

基于Dijistra算法的模拟过程

初始化 dist 数组：
定义一个 dist 数组，dist[i][j] 用于记录起点到 (i, j) 点的最短时间。初始时，起点到达自身位置的时间为0，到达其余点的时间为无限大 MAX。
从起点出发探索：
从起点出发，此时可以向上下左右四个方向探索。由于探索位置不能越界，因此当前用例起点只能向下和向右探索。由于是初始探索，因此不需要等待，到达新位置只需要花费 timePerRoad 时间。
选择新的源点并探索：
接下来有两个点可以当成新的源点，根据 Dijistra 算法，选择其中较小权重（时间）的点作为源点。此时由于两点权重（时间）相同，任选一个都可以。

比如选择 (1,0) 点作为新的源点，此时该点可以向下和向右探索：
- 向下的话，则是直线运动，需要等待，此时需要花费 timePerRod + lights[1][1] 的时间。
- 向右的话，则是左转运动，需要等待，此时需要花费 timePerRod + lights[1][1] 的时间。

继续选择源点并探索：
接下来，需要从多个时间值中选择最小的作为源点进行探索，该点只能向右和向下探索：
- 向右的话，则是直线运动，需要等待，此时需要花费 timePerRod + lights[0][1] 的时间。
- 向下的话，则是右转运动，不需要等待，此时仅需要花费 timePerRod 时间。即起点 (0,0) 到达 (1,1) 沿当前路径只需要120时间，要比之前探索的124小，根据 Dijistra 算法，更新 dist[]。
后续探索过程：
按照上述规则继续选择源点并探索，会出现一个问题。例如，当更新 (1, 2) 位置的时间时，如果按照 Dijistra 算法的逻辑更新，最终起点 (0,0) 到终点 (2,2) 的最短时间为248。但实际上，如果不更新 (1,2) 位置的时间（即保持 dist[1][2] = 185），最终起点 (0,0) 到终点 (2,2) 的最短时间为245，相较于 Dijistra 算法得出的最优选择，时间更短。

问题本质
本题的街道本质上是一个动态边权的有权图，两个点之间的边权，会因为第三个点的加入而改变，因此边权是动态的。而 Dijistra 算法无法处理这种情况。

解决方案
本题的 n 和 m 的范围为 [1,9]，不是很大，因此可以进行暴力搜索所有起点到终点的路径，并根据拐弯规则计算动态边权，得出最短时间的路径。例如采用深度优先搜索（DFS）算法进行暴力搜索应该不会超时。

二、JavaScript算法源码

这段代码实现了一个迷宫路径问题的求解，通过暴力深度优先搜索（DFS）寻找从起点到终点的最短路径，计算走完全程的最小时间花费。以下是对代码的详细讲解和注释：

代码结构

输入部分
- 使用 readline 模块处理标准输入。
- 首先读取迷宫的行数 n 和列数 m。
- 读取每个位置上的交通信号灯的等待时间（存入二维数组 lights）。
- 读取每条路段的基本行走时间 timePerRoad。
- 读取起点和终点的坐标。
DFS 与核心逻辑
- 使用深度优先搜索（DFS）暴力尝试所有可能的路径，记录最小的时间花费。
- 使用辅助数组 visited 防止回路。
- 通过向量叉积判断路径是否左拐、右拐或直行，计算等待时间。
辅助函数
- getDirection：判断三点之间的拐弯方向。
- dfs：递归搜索路径，计算花费时间并更新最优解。

详细代码讲解

输入处理

const [n, m] = (await readline()).split(" ").map(Number);
const lights = [];
for (let i = 0; i < n; i++) {
  lights.push((await readline()).split(" ").map(Number));
}
const timePerRoad = parseInt(await readline());
const [rowStart, colStart] = (await readline()).split(" ").map(Number);
const [rowEnd, colEnd] = (await readline()).split(" ").map(Number);

首先读取二维网格的大小 n 和 m。
然后读取网格中每个位置的交通信号灯所需等待时间，存储在二维数组 lights 中。
每条路的基本行走时间存储在变量 timePerRoad 中。
最后读取起点和终点的坐标。

数据结构

const visited = new Array(n).fill(0).map(() => new Array(m).fill(false));
const offsets = [
  [-1, 0], // 上
  [1, 0],  // 下
  [0, -1], // 左
  [0, 1],  // 右
];

visited 是一个二维布尔数组，用于标记某个位置是否已经访问，防止重复走回头路。
offsets 是一个方向数组，定义了从当前位置出发可以向上下左右四个方向移动。

主逻辑：`getResult` 和 `dfs`

function getResult() {
  visited[rowStart][colStart] = true;
  const minCost = [Infinity];
  dfs(rowStart, colStart, -1, -1, 0, minCost);
  return minCost[0];
}

标记起点为已访问。
定义 minCost 数组存储从起点到终点所需的最小时间，初始值为正无穷大（Infinity）。
调用 dfs 函数，开始递归搜索所有可能的路径。
最后返回 minCost[0]，即最短时间。

深度优先搜索：`dfs`

function dfs(curX, curY, preX, preY, cost, minCost) {
  if (cost >= minCost[0]) {
    return;
  }

  if (curX == rowEnd && curY == colEnd) {
    minCost[0] = cost;
    return;
  }

  for (let [offsetX, offsetY] of offsets) {
    const nextX = curX + offsetX;
    const nextY = curY + offsetY;

    if (
      nextX < 0 ||
      nextX >= n ||
      nextY < 0 ||
      nextY >= m ||
      visited[nextX][nextY]
    )
      continue;

    visited[nextX][nextY] = true;

    const direction = getDirection(preX, preY, curX, curY, nextX, nextY);

    let increment = timePerRoad;
    if (preX >= 0 && preY >= 0 && direction >= 0) {
      increment += lights[curX][curY];
    }

    dfs(nextX, nextY, curX, curY, cost + increment, minCost);

    visited[nextX][nextY] = false;
  }
}

退出条件：
- 如果当前路径的花费时间已经大于等于 minCost，则直接返回，避免无效计算。
- 如果到达终点，尝试更新 minCost。
递归探索：
- 遍历当前位置的四个方向，计算下一步移动位置 nextX 和 nextY。
- 如果新位置越界或已访问，则跳过。
- 标记新位置为已访问。
时间计算：
- 每次移动必须增加 timePerRoad 时间。
- 如果发生左拐或直行，则增加交通信号灯时间 lights[curX][curY]。
递归调用：
- 递归进入下一位置。
- 回溯时将新位置标记为未访问。

辅助函数：`getDirection`

function getDirection(preX, preY, curX, curY, nextX, nextY) {
  const dx1 = curX - preX;
  const dy1 = curY - preY;
  const dx2 = nextX - curX;
  const dy2 = nextY - curY;

  return dx1 * dy2 - dx2 * dy1;
}

使用向量的叉积判断拐弯方向：
- 0：向左拐。
- == 0：直行或调头。
- < 0：向右拐。

总结

这段代码通过暴力搜索所有可能的路径，求解从起点到终点的最短时间。其核心是使用深度优先搜索（DFS）递归地探索路径，同时结合交通信号灯等待时间的计算。虽然暴搜方法效率较低，但逻辑清晰且直观，适用于规模较小的问题。

三、Java算法源码

代码详细讲解

这段代码实现了一个基于深度优先搜索（DFS）的路径搜索算法，用于在一个二维网格中找到从起点到终点的最短时间路径。路径的代价不仅包括移动的时间，还包括在特定位置等待的时间。以下是代码的详细讲解：

1. 变量定义

static int n;
static int m;
static int[][] lights;
static int timePreRoad;
static int rowStart;
static int colStart;
static int rowEnd;
static int colEnd;

static boolean[][] visited;
static int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

n 和 m：分别表示网格的行数和列数。
lights：一个二维数组，表示每个位置的等待时间。
timePreRoad：表示每移动一步所需的时间。
rowStart 和 colStart：起点的行和列坐标。
rowEnd 和 colEnd：终点的行和列坐标。
visited：一个二维布尔数组，用于记录哪些位置已经被访问过，防止重复访问。
offsets：表示四个可能的移动方向（上、下、左、右）。

2. 主函数 `main`

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    n = sc.nextInt();
    m = sc.nextInt();

    lights = new int[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            lights[i][j] = sc.nextInt();
        }
    }

    timePreRoad = sc.nextInt();

    rowStart = sc.nextInt();
    colStart = sc.nextInt();

    rowEnd = sc.nextInt();
    colEnd = sc.nextInt();

    System.out.println(getResult());
}

从标准输入读取网格的大小 n 和 m。
读取每个位置的等待时间并存储在 lights 数组中。
读取每移动一步所需的时间 timePreRoad。
读取起点和终点的坐标。
调用 getResult() 方法并输出结果。

3. `getResult` 方法

public static int getResult() {
    visited = new boolean[n][m];
    visited[rowStart][colStart] = true;

    int[] minCost = {Integer.MAX_VALUE};
    dfs(rowStart, colStart, -1, -1, 0, minCost);
    return minCost[0];
}

初始化 visited 数组，并将起点标记为已访问。
定义一个数组 minCost 来记录从起点到终点的最小时间花费，初始值为 Integer.MAX_VALUE。
调用 dfs 方法进行深度优先搜索。
返回 minCost[0]，即最小时间花费。

4. `dfs` 方法

public static void dfs(int curX, int curY, int preX, int preY, int cost, int[] minCost) {
    if (cost >= minCost[0]) {
        return;
    }

    if (curX == rowEnd && curY == colEnd) {
        minCost[0] = cost;
        return;
    }

    for (int[] offset : offsets) {
        int nextX = curX + offset[0];
        int nextY = curY + offset[1];

        if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m || visited[nextX][nextY]) continue;

        visited[nextX][nextY] = true;

        int direction = getDirection(preX, preY, curX, curY, nextX, nextY);

        int increment = timePreRoad;
        if (preX >= 0 && preY >= 0 && direction >= 0) {
            increment += lights[curX][curY];
        }

        dfs(nextX, nextY, curX, curY, cost + increment, minCost);

        visited[nextX][nextY] = false;
    }
}

curX 和 curY：当前所在的位置。
preX 和 preY：上一个位置。
cost：到达当前位置所花费的时间。
minCost：记录从起点到终点的最小时间花费。
剪枝：如果当前路径的时间花费 cost 已经大于或等于已知的最小时间花费 minCost[0]，则停止继续搜索。
终止条件：如果当前位置是终点，并且当前路径的时间花费 cost 小于 minCost[0]，则更新 minCost[0]。
遍历四个方向：对于当前点的四个相邻位置，检查是否越界或已经访问过。如果没有越界且未被访问过，则标记为已访问，并计算移动到该位置的时间花费。
方向判断：通过 getDirection 方法判断移动方向，决定是否需要增加等待时间。
递归调用：递归调用 dfs 方法继续搜索。
回溯：在递归返回后，取消标记，以便其他路径可以访问该位置。

5. `getDirection` 方法

public static int getDirection(int preX, int preY, int curX, int curY, int nextX, int nextY) {
    int dx1 = curX - preX;
    int dy1 = curY - preY;

    int dx2 = nextX - curX;
    int dy2 = nextY - curY;

    return dx1 * dy2 - dx2 * dy1;
}

通过计算两个向量的叉积来判断移动方向：
- 如果叉积大于 0，表示向左拐。
- 如果叉积等于 0，表示直行（包括调头）。
- 如果叉积小于 0，表示向右拐。

6. 总结

这段代码通过深度优先搜索（DFS）遍历所有可能的路径，结合剪枝策略和方向判断，找到从起点到终点的最短时间路径。路径的代价包括移动时间和在特定位置的等待时间。通过回溯和方向判断，确保搜索过程高效且准确。

四、Python算法源码

代码详细讲解

这段代码是用 Python 实现的深度优先搜索（DFS）算法，用于在一个二维网格中找到从起点到终点的最短时间路径。路径的代价不仅包括移动的时间，还包括在特定位置等待的时间。以下是代码的详细讲解：

1. 输入获取

n, m = map(int, input().split())
lights = [list(map(int, input().split())) for _ in range(n)]
timePerRoad = int(input())
rowStart, colStart = map(int, input().split())
rowEnd, colEnd = map(int, input().split())

n 和 m：分别表示网格的行数和列数。
lights：一个二维列表，表示每个位置的等待时间。
timePerRoad：表示每移动一步所需的时间。
rowStart 和 colStart：起点的行和列坐标。
rowEnd 和 colEnd：终点的行和列坐标。

2. 全局变量

offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))
visited = [[False] * m for _ in range(n)]

offsets：表示四个可能的移动方向（上、下、左、右）。
visited：一个二维布尔列表，用于记录哪些位置已经被访问过，防止重复访问。

3. 方向判断函数 `getDirection`

def getDirection(preX, preY, curX, curY, nextX, nextY):
    dx1 = curX - preX
    dy1 = curY - preY

    dx2 = nextX - curX
    dy2 = nextY - curY

    return dx1 * dy2 - dx2 * dy1

功能：根据前一个点、当前点和下一个点的坐标，判断移动方向。
返回值：
- 如果返回值大于 0，表示向左拐。
- 如果返回值等于 0，表示直行（包括调头）。
- 如果返回值小于 0，表示向右拐。
实现原理：通过计算两个向量的叉积来判断方向。

4. 深度优先搜索函数 `dfs`

def dfs(curX, curY, preX, preY, cost, minCost):
    if cost >= minCost[0]:
        return

    if curX == rowEnd and curY == colEnd:
        minCost[0] = cost
        return

    for offsetX, offsetY in offsets:
        nextX = curX + offsetX
        nextY = curY + offsetY

        if nextX < 0 or nextX >= n or nextY < 0 or nextY >= m or visited[nextX][nextY]:
            continue

        visited[nextX][nextY] = True

        direction = getDirection(preX, preY, curX, curY, nextX, nextY)

        increment = timePerRoad
        if preX >= 0 and preY >= 0 and direction >= 0:
            increment += lights[curX][curY]

        dfs(nextX, nextY, curX, curY, cost + increment, minCost)

        visited[nextX][nextY] = False

参数：
- curX 和 curY：当前所在的位置。
- preX 和 preY：上一个位置。
- cost：到达当前位置所花费的时间。
- minCost：记录从起点到终点的最小时间花费。
功能：
- 如果当前路径的时间花费 cost 已经大于或等于已知的最小时间花费 minCost[0]，则停止继续搜索（剪枝）。
- 如果当前位置是终点，并且当前路径的时间花费 cost 小于 minCost[0]，则更新 minCost[0]。
- 遍历当前点的四个相邻位置，检查是否越界或已经访问过。如果没有越界且未被访问过，则标记为已访问，并计算移动到该位置的时间花费。
- 根据 getDirection 方法判断移动方向，决定是否需要增加等待时间。
- 递归调用 dfs 方法继续搜索。
- 在递归返回后，取消标记，以便其他路径可以访问该位置（回溯）。

5. 算法入口函数 `getResult`

def getResult():
    visited[rowStart][colStart] = True

    minCost = [sys.maxsize]
    dfs(rowStart, colStart, -1, -1, 0, minCost)

    return minCost[0]

功能：
- 初始化 visited 数组，并将起点标记为已访问。
- 定义一个列表 minCost 来记录从起点到终点的最小时间花费，初始值为 sys.maxsize（表示一个很大的数）。
- 调用 dfs 方法进行深度优先搜索。
- 返回 minCost[0]，即最小时间花费。

6. 算法调用

print(getResult())

调用 getResult 方法并输出结果。

代码总结

关键点：

方向判断：通过向量叉积判断移动方向，决定是否需要增加等待时间。
剪枝：如果当前路径的时间花费已经大于已知的最小时间花费，则停止继续搜索。
回溯：在递归返回后，取消标记，以便其他路径可以访问该位置。
时间复杂度：由于是暴力搜索，最坏情况下时间复杂度为 (O(4^{n imes m}))，但通过剪枝和方向判断，实际运行效率会有所提升。

如果你有其他问题，欢迎随时提问！

五、C/C++算法源码：

C++ 代码

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

const int MAX_SIZE = 10;

int n, m;
int lights[MAX_SIZE][MAX_SIZE];
int timePerRoad;
int rowStart, colStart;
int rowEnd, colEnd;

int offsets[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上、下、左、右方向偏移量

bool visited[MAX_SIZE][MAX_SIZE] = {false};

/*!
 * 根据三点坐标，确定拐弯方向
 * @param preX 前一个点横坐标
 * @param preY 前一个点纵坐标
 * @param curX 当前点横坐标
 * @param curY 当前点纵坐标
 * @param nextX 下一个点横坐标
 * @param nextY 下一个点纵坐标
 * @return cur到next的拐弯方向， >0 表示向左拐， ==0 表示直行（含调头）， <0 表示向右拐
 */
int getDirection(int preX, int preY, int curX, int curY, int nextX, int nextY) {
    int dx1 = curX - preX;
    int dy1 = curY - preY;

    int dx2 = nextX - curX;
    int dy2 = nextY - curY;

    return dx1 * dy2 - dx2 * dy1; // 叉积
}

/*!
 * 深度优先搜索
 * @param curX 当前点横坐标
 * @param curY 当前点纵坐标
 * @param preX 上一个点横坐标
 * @param preY 上一个点纵坐标
 * @param cost 当前路径花费时间
 * @param minCost 记录最小花费时间
 */
void dfs(int curX, int curY, int preX, int preY, int cost, int &minCost) {
    if (cost >= minCost) // 如果当前路径消耗时间大于等于最小值，剪枝
        return;

    if (curX == rowEnd && curY == colEnd) { // 如果到达终点，更新最小值
        minCost = cost;
        return;
    }

    for (int i = 0; i < 4; i++) { // 遍历四个方向
        int nextX = curX + offsets[i][0];
        int nextY = curY + offsets[i][1];

        if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m || visited[nextX][nextY]) {
            continue; // 越界或已访问点，跳过
        }

        visited[nextX][nextY] = true; // 标记为已访问

        int direction = getDirection(preX, preY, curX, curY, nextX, nextY);
        int increment = timePerRoad;

        if (preX >= 0 && preY >= 0 && direction >= 0) { // 如果左拐或直行，加信号灯等待时间
            increment += lights[curX][curY];
        }

        dfs(nextX, nextY, curX, curY, cost + increment, minCost); // 递归搜索

        visited[nextX][nextY] = false; // 回溯，标记为未访问
    }
}

/*!
 * 计算最短路径时间
 * @return 最短时间
 */
int getResult() {
    visited[rowStart][colStart] = true; // 标记起点为已访问
    int minCost = INT_MAX; // 最小时间初始化为无穷大
    dfs(rowStart, colStart, -1, -1, 0, minCost); // 开始搜索
    return minCost;
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> lights[i][j];

    cin >> timePerRoad >> rowStart >> colStart >> rowEnd >> colEnd;

    cout << getResult() << endl;

    return 0;
}

C 代码

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

#define MAX_SIZE 10

int n, m;
int lights[MAX_SIZE][MAX_SIZE];
int timePerRoad;
int rowStart, colStart;
int rowEnd, colEnd;

int offsets[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上、下、左、右方向偏移量

int visited[MAX_SIZE][MAX_SIZE] = {0}; // 标记是否访问过

/*!
 * 根据三点坐标，确定拐弯方向
 */
int getDirection(int preX, int preY, int curX, int curY, int nextX, int nextY) {
    int dx1 = curX - preX;
    int dy1 = curY - preY;
    int dx2 = nextX - curX;
    int dy2 = nextY - curY;

    return dx1 * dy2 - dx2 * dy1; // 叉积计算方向
}

/*!
 * 深度优先搜索
 */
void dfs(int curX, int curY, int preX, int preY, int cost, int *minCost) {
    if (cost >= *minCost) // 剪枝
        return;

    if (curX == rowEnd && curY == colEnd) { // 到达终点
        *minCost = cost;
        return;
    }

    for (int i = 0; i < 4; i++) { // 遍历四个方向
        int nextX = curX + offsets[i][0];
        int nextY = curY + offsets[i][1];

        if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m || visited[nextX][nextY])
            continue;

        visited[nextX][nextY] = 1;

        int direction = getDirection(preX, preY, curX, curY, nextX, nextY);
        int increment = timePerRoad;

        if (preX >= 0 && preY >= 0 && direction >= 0) {
            increment += lights[curX][curY];
        }

        dfs(nextX, nextY, curX, curY, cost + increment, minCost);

        visited[nextX][nextY] = 0; // 回溯
    }
}

/*!
 * 计算最短路径时间
 */
int getResult() {
    visited[rowStart][colStart] = 1; // 起点标记已访问
    int minCost = INT_MAX; // 初始化最短时间为无穷大
    dfs(rowStart, colStart, -1, -1, 0, &minCost); // 搜索路径
    return minCost;
}

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

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &lights[i][j]);

    scanf("%d", &timePerRoad);
    scanf("%d %d", &rowStart, &colStart);
    scanf("%d %d", &rowEnd, &colEnd);

    printf("%d
", getResult());

    return 0;
}

代码讲解

输入数据：
- 读取二维网格大小 n 和 m。
- 读取信号灯等待时间矩阵 lights。
- 读取每条路段的基本行走时间 timePerRoad。
- 读取起点和终点坐标。
DFS 搜索逻辑：
- 使用递归深度优先算法，枚举所有可能的路径。
- 剪枝优化：如果当前路径时间已经超过最小值，则直接返回。
- 每次移动时，根据拐弯方向判断是否需要等待信号灯。
辅助函数：
- getDirection：通过三点坐标计算向量叉积，判断左拐、右拐或直行。
最小时间计算：
- 使用 dfs 遍历所有路径，返回最小消耗时间。

区别

C++ 代码 更加简洁，使用了 vector 等 STL 数据结构和流输入输出。
C 代码 使用数组和指针，手动管理递归过程中的变量。

六、尾言

什么是华为OD？

华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。

为什么刷题很重要？

机试是进入技术面的第一关：
华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。
技术面试需要手撕代码：
技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。
入职后的可信考试：
入职华为后，还需要通过“可信考试”。可信考试分为三个等级：
- 入门级：主要考察基础算法与编程能力。
- 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
- 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。

刷题策略与说明：

2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：

关注历年真题：
- 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
- 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。
适应新题目：
- E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
- 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。
掌握常见算法：
华为OD考试通常涉及以下算法和数据结构：
- 排序算法（快速排序、归并排序等）
- 动态规划（背包问题、最长公共子序列等）
- 贪心算法
- 栈、队列、链表的操作
- 图论（最短路径、最小生成树等）
- 滑动窗口、双指针算法
保持编程规范：
- 注重代码的可读性和注释的清晰度。
- 熟练使用常见编程语言，如C++、Java、Python等。

如何获取资源？

官方参考：
- 华为招聘官网或相关的招聘平台会有一些参考信息。
- 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。
加入刷题社区：
- 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
- 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。
寻找系统性的教程：
- 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
- 完成系统的学习课程，例如数据结构与算法的在线课程。

积极心态与持续努力：

刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。

考试注意细节

本地编写代码
- 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。
调整心态，保持冷静
- 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。
输入输出完整性
- 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。
快捷键使用
- 删除行可用 Ctrl+D，复制、粘贴和撤销分别为 Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。
- 避免使用 Ctrl+S，以免触发浏览器的保存功能。
浏览器要求
- 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。
交卷相关
- 答题前，务必仔细查看题目示例，避免遗漏要求。
- 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
- 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。
时间和分数安排
- 总时间：150 分钟；总分：400 分。
- 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。
考试环境准备
- 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
- 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。
技术问题处理
- 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
- 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。

祝你考试顺利，取得理想成绩！

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

上一篇
从零到一学习c++（基础篇--筑基期六-strin...

下一篇
LeetCode-13.罗马数字转整数（C/C++）...

站长推荐

U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决
QT多线程的5种用法，通过使用线程解决UI主界面的耗时操作代码，防止界面卡死。
QT多线程的5种用法，通过使用线程解决UI主界面的耗时操作代码，防止界面卡死。...
stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程）
分享几个国内免费的ChatGPT镜像网址(亲测有效)
分享几个国内免费的ChatGPT镜像网址(亲测有效)
SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权

您现在的位置是：首页 >技术交流 >【2024年华为OD机试】(C卷,200分)- 路口最短时间问题 （JavaScript&Java & Python&C/C++）网站首页技术交流

【2024年华为OD机试】(C卷,200分)- 路口最短时间问题 （JavaScript&Java & Python&C/C++）

一、问题描述

二、JavaScript算法源码

代码结构

详细代码讲解

输入处理

数据结构

主逻辑：getResult 和 dfs

深度优先搜索：dfs

辅助函数：getDirection

总结

三、Java算法源码

代码详细讲解

1. 变量定义

2. 主函数 main

3. getResult 方法

4. dfs 方法

5. getDirection 方法

6. 总结

四、Python算法源码

代码详细讲解

1. 输入获取

2. 全局变量

3. 方向判断函数 getDirection

4. 深度优先搜索函数 dfs

5. 算法入口函数 getResult

6. 算法调用

代码总结

关键点：

五、C/C++算法源码：

C++ 代码

C 代码

代码讲解

区别

六、尾言

什么是华为OD？

为什么刷题很重要？

刷题策略与说明：

如何获取资源？

积极心态与持续努力：

考试注意细节

上一篇 从零到一学习c++（基础篇--筑基期六-strin...

下一篇 LeetCode-13.罗马数字转整数（C/C++）...

站长推荐

您现在的位置是：首页 >技术交流 >【2024年华为OD机试】(C卷,200分)- 路口最短时间问题（JavaScript&Java & Python&C/C++）网站首页技术交流

【2024年华为OD机试】(C卷,200分)- 路口最短时间问题（JavaScript&Java & Python&C/C++）

主逻辑：`getResult` 和 `dfs`

深度优先搜索：`dfs`

辅助函数：`getDirection`

2. 主函数 `main`

3. `getResult` 方法

4. `dfs` 方法

5. `getDirection` 方法

3. 方向判断函数 `getDirection`

4. 深度优先搜索函数 `dfs`

5. 算法入口函数 `getResult`

上一篇
从零到一学习c++（基础篇--筑基期六-strin...

下一篇
LeetCode-13.罗马数字转整数（C/C++）...