华为OD机试真题 - 寻找最优的路测线路 (D卷,200分)

题目描述

评估一个网络的信号质量，其中一个做法是将网络划分为栅格，然后对每个栅格的信号质量计算。

路测的时候，希望选择一条信号最好的路线（彼此相连的栅格集合）进行演示。

现给出 R 行 C 列的整数数组 Cov，每个单元格的数值 S 即为该栅格的信号质量（已归一化，无单位，值越大信号越好）。

要求从 [0, 0] 到 [R-1, C-1]设计一条最优路测路线。返回该路线得分。

规则：

1. 路测路线可以上下左右四个方向，不能对角
2. 路线的评分是以路线上信号最差的栅格为准的，例如路径 8→4→5→9 的值为4，该线路评分为4。线路最优表示该条线路的评分最高。

目录

题目描述

输入描述

输出描述

用例

题目解析

Java算法源码

JS算法源码

Python算法源码

C算法源码

华为机试有三道题目，第一道和第二道属于简单或中等题，分值为100分，第三道为中等或困难题，分值为200分。总分为400分，150分钟，机试是在牛客考试，练习的时候也可以在牛客网练习，提前熟悉操作

https://ac.nowcoder.com/acm/contest/5652/K

点击上方链接进入牛客练习界面，可以自定义题目，自定义输入、输出等等，华为OD真实机试环境，非其他第三方平台模拟。

输入描述

第一行表示栅格的行数 R

第二行表示栅格的列数 C

第三行开始，每一行表示栅格地图一行的信号值，如5 4 5

输出描述

最优路线的得分

备注

• 1 ≤ R，C ≤ 20
• 0 ≤ S ≤ 65535

用例

题目解析

1. 首先将输入的栅格地图转换为二维数组。
2. 初始化一个二维数组dp，用于记录从起点到每个栅格的最优路线得分。
3. 遍历栅格地图，对于每个栅格，计算从起点到该栅格的最优路线得分，并更新dp数组。
4. 最后返回dp数组中终点的值作为结果。

JS算法源码

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });

let lines = [];
rl.on('line', (line) => {
  lines.push(line);
});

rl.on('close', () => {
  const r = parseInt(lines[0]);
  const c = parseInt(lines[1]);

  const matrix = lines.slice(2, 2 + r).map(line => line.split(' ').map(Number));

  const dist = Array(r * c).fill(Infinity);
  dist[0] = matrix[0][0];

  const pq = [0];

  const offsets = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  while (pq.length > 0) {
    const u = pq.pop();

    const y = u % c;
    const x = Math.floor(u / c);

    if (x === r - 1 && y === c - 1) break;

    for (let [offsetX, offsetY] of offsets) {
      const newX = x + offsetX;
      const newY = y + offsetY;

      if (newX < 0 || newX >= r || newY < 0 || newY >= c) continue;

      const v = newX * c + newY;
      const w = Math.min(dist[u], matrix[newX][newY]);

      if (dist[v] > w) {
        dist[v] = w;
        pq.push(v);
      }
    }

    pq.sort((a, b) => dist[a] - dist[b]);
  }

  console.log(dist[r * c - 1]);
});

Java算法源码

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

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

    int r = sc.nextInt();
    int c = sc.nextInt();

    int[][] matrix = new int[r][c];
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
        matrix[i][j] = sc.nextIn